[POI2015]WIL-Wilcze doły（单调队列）

题意

给定一个长度为n的序列，你有一次机会选中一段连续的长度不超过d的区间，将里面所有数字全部修改为0。请找到最长的一段连续区间，使得该区间内所有数字之和不超过p。

(1<=d<=n<=2000000，0<=p<=10^16)

题解

一看以为是DP结果想了半天想不出来。（其实有点像）

然后又以为是单调队列套单调队列。。。（我也不知到这是什么）

但跟答案很像了，就差一点。

假如给定选择区间，一定要去掉和最大的连续d个数。

所以我们枚举以右端点r，用单调对列维护当前区间内最大的连续d个数的值。

在区间扩展时（r++）我们判断当前区间在去掉最大的连续d个数的值之后是否大于p

若大于p则l++更新单调队列。对于每一个右端点都有一个最优解。取最大就好了。

o(n)

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const long long N=;

 long long n,p,d,a[N],sum1[N],sum[N],q[N],l,head,tail,tot,ans;

 int main(){

     scanf("%lld%lld%lld",&n,&p,&d);

     for(long long i=;i<=n;i++){

         scanf("%lld",&a[i]);

         sum1[i]=sum1[i-]+a[i];

     }

     for(long long i=;i<=d;i++){

         sum[i]=sum1[i];

     }

     for(long long i=d+;i<=n;i++){

         sum[i]=sum1[i]-sum1[i-d];

     }

 //    for(int i=1;i<=n;i++){

 //        cout<<sum[i]<<" ";

 //    }

 //    cout<<endl;

     head=;

     tail=;

     l=;

     for(long long i=;i<=n;i++){

         tot+=a[i];

         while(sum[i]>=sum[q[tail]]&&head<=tail)tail--;

         q[++tail]=i;

         while(tot-sum[q[head]]>p&&head<=tail){

             tot-=a[l];

             l++;

             while(q[head]-d<l&&head<=tail)head++;

         }

         ans=max(ans,i-l+);

     }

     printf("%lld",ans);

     return ;

 }

巴特西

[POI2015]WIL-Wilcze doły（单调队列）

题意

题解

最新文章

热门文章