欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

关于单调队列的一些运用 洛谷P3594

程序员文章站 2022-05-09 13:47:06
...

题目大意:
给定一个长度为n的序列,你有一次机会选中一段连续的长度不超过d的区间,将里面所有数字全部修改为0。请找到最长的一段连续区间,使得该区间内所有数字之和不超过p。
数据范围:n<=2e6;
题解:
我们考虑对于j作为右端点,那么这个区间的左端点在右端点递增时具有单调递增性,可以用反证法证明。那么对于每一个右端点,我们要求出它的左端点即可,那么问题就转化成了求已知右端点与上次询问的左端点,求期间的长度为d权值最大的区间,然后根据是否满足要求来更新左端点,就能求出答案。
下面是今天的核心内容:单调队列
单调队列的要求是在队列中单调递增/递减,它的作用主要是维护一段区间内的合法最值,由于它是队列,其中保存了多个较优解,当区间更改后,也不会出现没有最优解的情况。其一般用于优化其他算法,主要是dp的优化,其中一般保留坐标,用坐标来提取权值,这样有利于更好的维护队列中所存区间合法。其单调性不仅是权值上的单调性,并且有合法上的单调性,即越后入队的弹出越晚,那么就可以很方便的清除不合法的区间。
这道题就按照题目要求和单调队列要求的维护就好了;

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=2e6+10;
deque<LL>q;
inline LL read()
{
    LL ret=0;char c=getchar();
    while(c<'0'||c>'9')	c=getchar();
    while(c>='0'&&c<='9')	ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
LL n,p,d,num[maxn],sum[maxn],sec[maxn];
int main()
{
    //freopen("4385.in","r",stdin);
    //freopen("4385.out","w",stdout);
    n=read(),p=read(),d=read();
    for(int i=1;i<=n;i++)	num[i]=read();
    for(int i=1;i<=n;i++)	sum[i]=sum[i-1]+num[i];
    for(int i=d;i<=n;i++)	sec[i-d+1]=sum[i]-sum[i-d];
    q.push_front(1);LL last=1,ans=d;
    for(int i=2;i<=n-d+1;i++){
        while(!q.empty()&&sec[i]>sec[q.back()])	q.pop_back();
        q.push_back(i);
        while(!q.empty()&&last>q.front())	q.pop_front();
        while(!q.empty()&&sum[i+d-1]-sum[last-1]-sec[q.front()]>p){
            last++;
            if(!q.empty()&&last>q.front())	q.pop_front();
        }
        ans=max(ans,i+d-1-(last-1));
    }
    printf("%lld",ans);
    return 0;
}
相关标签: 洛谷