【BZOJ2600】【IOI2011】Rice Hub

  二分答案，或者two-point。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100010;

int n,len;
long long b;
int X[maxn];
long long sum[maxn];
int ans;

long long Calc(int l,int r)
{
	int mid=(l+r)>>1;
	return (sum[r]-sum[mid])-(sum[mid-1]-sum[l-1])-(((r-l)&1)?X[mid]:0);
}

int main()
{
	scanf("%d%d%lld",&n,&len,&b);
	for (int i=1;i<=n;i++) scanf("%d",&X[i]),sum[i]=sum[i-1]+X[i];
	for (int l=1,r=1;l<=n;l++)
	{
		while (r<n && Calc(l,r+1)<=b) r++;
		if (Calc(l,r)<=b && r-l+1>ans) ans=r-l+1;
	}
	printf("%d\n",ans);
	return 0;
}