bzoj2086【Poi2010】Blocks

因为long long还有PE的事WA了一下午TAT

考虑一段可行区间的平均值肯定>=k

也就是说将每个数减去k以后,一段可行区间的和非负,求一段最长区间。

一段区间的和肯定是两个前缀和的差

先求出前缀和,考虑要想让答案更优,被减数应该靠后而且大,减数应该靠前而且小

so维护两个单调队列然后two-pointers扫一遍就好了QwQ~

记得输出行末必须换行&不能有空格

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
const int Mx=;
struct Node { int val,num; } stk1[Mx],stk2[Mx];
int n,m,cnt1,cnt2,c[Mx],num[Mx],sum[Mx];
void solve(int k)
{
cnt1=,cnt2=;
memset(stk1,,sizeof(stk1));
memset(stk2,,sizeof(stk2));
int tmp=-898892147483647LL,ans=;
for(int i=;i<=n;i++) num[i]=c[i]-k;
for(int i=;i<=n;i++) sum[i]=sum[i-]+num[i];
for(int i=n;i>=;i--) if(sum[i]>tmp) stk1[++cnt1].val=sum[i],stk1[cnt1].num=i,tmp=sum[i];
tmp=2147889998483647LL;
for(int i=;i<=n;i++) if(sum[i]<tmp) stk2[++cnt2].val=sum[i],stk2[cnt2].num=i,tmp=sum[i];
for(int st=cnt1,to=;st>=&&to<=cnt2;st--)
{
while()
{
if(stk1[st].val-stk2[to].val>=)
{
ans=max(ans,stk1[st].num-stk2[to].num);
break;
}
else to++;
}
}
printf("%lld",ans);
}
signed main()
{
//freopen("1.in","r",stdin);
scanf("%lld%lld",&n,&m);
for(int i=;i<=n;i++) scanf("%lld",&c[i]);
while(m--)
{
int k;scanf("%lld",&k);
solve(k);
if(m)printf(" ");
else puts("");
}
return ;
}
上一篇:Spark 学习笔记1 (常见术语 )


下一篇:python中web应用与mysql数据库交互