2585283

本站停用,新站已更换地址
http://limohan.cn/
本站点留作纪念

©2585283
Powered by LOFTER
 

[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

  1. #include <cstdio>

  2. #include <algorithm>

  3. #include <iostream>

  4. #define rg register int

  5. #define ll long long

  6. using namespace std;

  7. const int maxn = 1000006;

  8. int a[maxn], q[maxn];

  9. ll sum[maxn];

  10. int n, m, top;

  11. void solve(int x)

  12. {

  13.   int ans = 0;

  14.   for(rg i = 1; i <= n; i++)

  15.   sum[i] = sum[i-1] + a[i] - x;

  16.   top = 0;

  17.   for(rg i = 1; i <= n; i++)

  18.   if(sum[q[top]] > sum[i])

  19.   q[++top] = i;

  20.   for(rg i = n, j = top; i >= 0; i--)

  21.   {

  22.     while(j && sum[i] >= sum[q[j-1]])j--;

  23.     ans = max(ans, i - q[j]);

  24.   }

  25.   printf("%d", ans);

  26. }

  27. int main()

  28. {

  29.   scanf("%d %d", &n, &m);

  30.   for(rg i = 1; i <= n; i++)

  31.   scanf("%d", &a[i]);

  32.   while(m--)

  33.   {

  34.     int x = 0;

  35.     scanf("%d", &x);

  36.     solve(x);

  37.     if(m)printf(" ");

  38.   }

  39.   return 0;

  40. }