题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2086
如果一段前缀和>=k*len那么就是可行的。
于是对所有的a[i]-=k，求前缀和。然后从1~n维护一个单调递减的栈。
从n~1扫一遍，如果sum[i]-sum[q[top-1]]>=0，那么以q[top-1]作为左端点是更优的
#include<cstring> #include<cstdio> #include<iostream> #include<algorithm> #include<cmath> #include<queue> #define rep(i,l,r) for (int i=l;i<=r;i++) #define down(i,l,r) for (int i=l;i>=r;i--) #define clr(x,y) memset(x,y,sizeof(x)) #define inf int(1e9) #define maxn 1005000 #define mm 30031 #define ll long long using namespace std; int n,m,top; ll k; ll a[maxn],sum[maxn]; int q[maxn]; ll read(){ ll x=0,f=1; char ch=getchar(); while (!isdigit(ch)) {if (ch==‘-‘) f=-1; ch=getchar();} while (isdigit(ch)) {x=x*10+ch-‘0‘; ch=getchar();} return x*f; } int main(){ n=read(); m=read(); rep(i,1,n) a[i]=read(); rep(i,1,m){ k=read(); rep(j,1,n) sum[j]=sum[j-1]+a[j]-k; top=0; rep(j,1,n) if (sum[q[top]]>sum[j]) q[++top]=j; int ans=0; down(j,n,1){ while (top&&sum[j]-sum[q[top-1]]>=0) top--; ans=max(ans,j-q[top]); } if (i!=m) printf("%d ",ans); else printf("%d\n",ans); } return 0; }
原文：http://www.cnblogs.com/ctlchild/p/5049352.html