「BZOJ2086」[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
1 2 1 1 5
1 2 3 4 5 6
Sample Output
5 5 2 1 1 0
题解
显然一段的平均数超过K即为合法解
将a[i]减去K，求其前缀和
若i>j且sum[i]>=sum[j]则j作为左端点比i更优
所以只要维护一个sum的单调递减栈，一个指针从n->0，不断弹栈，更新答案
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include<cmath> #include<queue> #include<vector> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define pa pair<int,int> #define inf 1000000000 #define eps 1e-8 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,top; int a[1000005],q[1000005]; ll sum[1000005]; void solve(int x) { int ans=0; for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i]-x; top=0; for(int i=1;i<=n;i++) if(sum[q[top]]>sum[i])q[++top]=i; for(int 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() { n=read();m=read(); for(int i=1;i<=n;i++) a[i]=read(); while(m--) { int x=read(); solve(x); if(m)printf(" "); else puts(""); } return 0; } |
Subscribe
计数器 9786167
OI 课件=>
OI 课件=>