Description
给出N个正整数a[1..N]，再给出一个正整数k，现在可以进行如下操作：每次选择一个大于k的正整数a[i]，将a[i]减去1，选择a[i-1]或a[i+1]中的一个加上1。经过一定次数的操作后，问最大能够选出多长的一个连续子序列，使得这个子序列的每个数都不小于k。
总共给出M次询问，每次询问给出的k不同，你需要分别回答。
Input
第一行两个正整数N (N <= 1,000,000)和M (M <= 50)。
第二行N个正整数，第i个正整数表示a[i] (a[i] <= 10^9)。
第三行M个正整数，第i个正整数表示第i次询问的k (k <= 10^9)。
Output
共一行，输出M个正整数，第i个数表示第i次询问的答案。
Sample Input
5 6
1 2 1 1 5
1 2 3 4 5 6
1 2 1 1 5
1 2 3 4 5 6
Sample Output
5 5 2 1 1 0
Bzoj权限题。目前只测了样例。
和操作次数没有关系。分析一波可以知道，只要一段的平均数大于k，就有解。
维护一个前缀和数组（累加每一项时都减去k），然后在这个数组里维护一个单增的单调栈求解。
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #define LL long long 7 using namespace std; 8 const int mxn=1000020; 9 int n,m; 10 int a[mxn];LL sum[mxn]; 11 int k; 12 int ans; 13 int st[mxn],top; 14 void solve(){ 15 int i; 16 for(i=1;i<=n;i++)sum[i]=sum[i-1]+a[i]-k; 17 top=0; 18 for(i=1;i<=n;i++)if(sum[st[top]]>sum[i])st[++top]=i;//前缀和更大，则入栈 19 for(i=n;i>=0;i--){ 20 while(top && (sum[i]>=sum[st[top-1]]))top--;//长度尽可能大 21 ans=max(ans,i-st[top]); 22 } 23 return; 24 } 25 int main(){ 26 scanf("%d%d",&n,&m); 27 int i,j; 28 for(i=1;i<=n;i++) scanf("%d",&a[i]); 29 for(i=1;i<=m;i++){ 30 scanf("%d",&k); 31 ans=0; 32 solve(); 33 printf("%d ",ans); 34 } 35 return 0; 36 }