首页 > 代码库 > BZOJ 2086: [Poi2010]Blocks
BZOJ 2086: [Poi2010]Blocks
Description
每次可以将大于 \(k\) 的一个数 \(-1\), 在左边或右边的数 \(+1\) ,问最大能得到多长的序列每个数都大于等于 \(k\) .
Sol
单调栈.
这道题好神啊qwq...思路++
首先如果一段序列满足 \(\sum_{i=l}^ri \geqslant k(r-l+1)\) 那么这个序列就是合法的,把所有的数都 \(-k\) 那么只需要满足非负即可.
然后从前往后找一个单调递减的前缀和序列,如果有小于等于前面的某个位置的前缀和,那么选这个不如选前面大于等于他的那个位置.
然后倒着做,右端点递减的时候,左端点要满足递减才能对答案产生贡献,就用一个栈来维护就行.
Code
/************************************************************** Problem: 2086 User: BeiYu Language: C++ Result: Accepted Time:4768 ms Memory:20820 kb****************************************************************/ #include <bits/stdc++.h>using namespace std; typedef long long LL;const int N = 1e6+50; LL n,m,ans;LL a[N],s[N];int stk[N],top; inline LL in(LL x=0,char ch=getchar()) { while(ch>‘9‘ || ch<‘0‘) ch=getchar(); while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();return x; }int main() { n=in(),m=in(); for(int i=1;i<=n;i++) a[i]=in(); for(;m--;) { LL x=in();top=0,ans=0; for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]-x; for(int i=1;i<=n;i++) if(s[i]<s[stk[top]]) stk[++top]=i; for(int i=n;i>=0;i--) { while(top && s[i]-s[stk[top-1]]>=0) top--; ans=max(ans,(LL)i-stk[top]); }printf("%lld%c",ans,"\n "[m>0]); } return 0;}
BZOJ 2086: [Poi2010]Blocks
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。