最高的牛

题目

题目

题解

这道题目我是真的觉得比较难QAQ。

首先，对于(A,B(A<B))能互相看到，肯定不存在(x,y(A<x<B,y>B或者y<A))能互相看到，所以(A,B)互相看到其实就划分了一个区域了，所以对于(A,B)能够看见，中间的数字的(f)就要小于(min(f[A],f[B]))，所以不难相出其实对于一个点(x)的(f)，(f)的最大值就是(H-k)（(k)为覆盖了(x)的(A,B)对数），那么我们就要找一种运算处理这种关系，没错，就是(-)号，我们让(A+1,B-1)之间的数字的(f)全部减一（其实就是这些数字的(k)全部加了一），当然，这些操作都只需要用差分就可以处理了，最后跑一遍前缀和即可。

竟然(A)可以大于(B)！(╯‵□′)╯︵┻━┻

还有(P)有个毛用啊(╯‵□′)╯︵┻━┻

(A,B)还可能重复(╯‵□′)╯︵┻━┻

代码

时间复杂度：(O(n))

#include<cstdio>
#define  N  11000
using  namespace  std;
struct  node
{
	int  a,b;
}b[N];
inline  bool  cmp(node  x,node  y){return  (x.a==y.a)?x.b<y.b:x.a<y.a;}
int  a[N];
int  main()
{
	int  n,k,p,m;scanf("%d%d%d%d",&n,&k,&p,&m);
	a[1]+=p;
	for(int  i=1;i<=m;i++)
	{
		int  x,y;scanf("%d%d",&x,&y);
		if(x>y)x^=y^=x^=y; 
		b[i].a=x;b[i].b=y;
	}
	for(int  i=1;i<=m;i++)
	{
		if(b[i].a!=b[i-1].a  ||  b[i].b!=b[i-1].b)a[b[i].a+1]--,a[b[i].b]++; 
	}
	for(int  i=1;i<=n;i++)a[i]+=a[i-1];
	for(int  i=1;i<=n;i++)printf("%d
",a[i]);
	return  0;
}