首页 > 代码库 > BZOJ2086: [Poi2010]Blocks
BZOJ2086: [Poi2010]Blocks
题解：
想了想发现只需要求出最长的一段平均值>k即可。
平均值的问题给每个数减去k，判断是否连续的一段>0即可。
然后我们发现如果i<j 且 s[i]<s[j]，那么 j 对于l>j不会比i 优。
那我们就可以维护一个单调的s[i]，然后对于每个l去二分出它的答案。
但这样会T。
再次考虑单调性。
如果 l>j，且s[l]>s[i]，那么我们的答案最小也是l-i，所以j必须取比i小的s才有可能更新答案。然后就可以两个指针扫一遍了。
好吧 我承认我口胡。。。
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 1000000+514 #define maxm 1000000+515 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)23 #define mod 100000000724 using namespace std;25 inline ll read()26 {27 ll x=0,f=1;char ch=getchar();28 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}29 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}30 return x*f;31 }32 int n,m,q[maxn];33 ll a[maxn],b[maxn];34 int main()35 {36 freopen("input.txt","r",stdin);37 freopen("output.txt","w",stdout);38 n=read();m=read();39 for1(i,n)a[i]=read();40 while(m--)41 {42 ll x=read();int r=0;43 q[r=1]=b[0]=0;44 for1(i,n)45 {46 b[i]=b[i-1]+a[i]-x;47 if(b[i]<b[q[r]])q[++r]=i;48 }49 int ans=0;50 for(int i=n;i>0&&r;i--)51 {52 while(r&&b[i]>=b[q[r]])r--;53 r++;54 if(b[i]>=b[q[r]])ans=max(ans,i-q[r]);55 }56 printf("%d",ans);if(m)printf(" ");else printf("\n");57 }58 return 0;59 }
2086: [Poi2010]Blocks
Time Limit: 20 Sec Memory Limit: 259 MBSubmit: 199 Solved: 91
[Submit][Status]
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
BZOJ2086: [Poi2010]Blocks
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。