[BZOJ2086/Luogu3503][POI2010] Blocks
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
Sample Output
5 5 2 1 1 0
Solution
显然一段的平均数超过K即为合法解
将a[i]减去K,求其前缀和
若i>j且sum[i]>=sum[j]则j作为左端点比i更优
所以只要维护一个sum的单调递减栈,一个指针从n->0,不断弹栈,更新答案
Std
#include <cstdio>
#include <algorithm>
#include <iostream>
#define rg register int
#define ll long long
using namespace std;
const int maxn = 1000006;
int a[maxn], q[maxn];
ll sum[maxn];
int n, m, top;
void solve(int x)
{
int ans = 0;
for(rg i = 1; i <= n; i++)
sum[i] = sum[i-1] + a[i] - x;
top = 0;
for(rg i = 1; i <= n; i++)
if(sum[q[top]] > sum[i])
q[++top] = i;
for(rg i = n, j = top; i >= 0; i--)
{
while(j && sum[i] >= sum[q[j-1]])j--;
ans = max(ans, i - q[j]);
}
printf("%d", ans);
}
int main()
{
scanf("%d %d", &n, &m);
for(rg i = 1; i <= n; i++)
scanf("%d", &a[i]);
while(m--)
{
int x = 0;
scanf("%d", &x);
solve(x);
if(m)printf(" ");
}
return 0;
}