高橋・直樹's Blog

http://www.lydsy.com/JudgeOnline/problem.php?id=2600

题意

n片稻田，分别位于x[i],建一个谷仓，使得总代价不大于b的情况下，控制的稻田最多，总代价定义为所有稻田到谷仓的距离和。

题解

IOI最弱题。

1.对于选出的稻田集合S，建在他们的中位数的位置最优

2.显然选连续的稻田更优，此时cost可以前缀和O(1)

3.所以O(n)扫过去就可以了

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100001;
int a[N],l,r,ans;
long long s[N],b;
long long cost(int l,int r)
{
	int m=l+r>>1;
	long long tmp=(m-l+1)*a[m]-(s[m]-s[l-1])+(s[r]-s[m])-(r-m)*a[m];
	return tmp;
}
int main()
{
	scanf("%d%d%lld",&r,&l,&b);
	for(int i=1;i<=r;i++)
		scanf("%d",a+i),s[i]=s[i-1]+a[i];
	for(int i=1,j=1;j<=r;j++)
	{
		while(cost(i,j)>b) i++;
		ans=max(ans,j-i+1);
	}
	printf("%d\n",ans);
}