即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

bzoj 4385: [POI2015]Wilcze doły 单调队列

编程语言 qq_33229466 10℃ 0评论
本文目录
[隐藏]

1.题意

给定一个长度为n的序列,你有一次机会选中一段连续的长度不超过d的区间,将里面所有数字全部修改为0。


请找到最长的一段连续区间,使得该区间内所有数字之和不超过p。


1<=d<=n<=2000000,0<=p<=10^16,1<=w[i]<=10^9

2.分析

首先考虑没有机会时要怎么做,显然可以用双指针乱搞。


那加上了机会呢?显然也是可以双指针乱搞。


显然随着右端点不断递增,左端点是不递减的。考虑如何维护左端点。


显然一个区间[l,r]用掉机会的最小和等于s[r]-s[l-1]-max(c[l+d-1..r])


c[i]表示sum(a[i-d+1..i])


那么用单调队列维护c的最大值即可。

3.代码

#include
#include
#include
#include
#include
using namespace std;

typedef long long LL;

const int N=2000005;

int n,d,head,tail,q2[N];
LL q1[N],a[N],p;

int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int main()
{
    n=read();scanf("%lld",&p);d=read();
    for (int i=1;i<=n;i++) a[i]=read(),a[i]+=a[i-1];
    int ans=d,l=1,r=d,head=1,tail=1;q1[tail]=a[d];q2[tail]=d;
    while (rwhile (head<=tail&&q1[tail]<=a[r]-a[r-d]) tail--;
        q1[++tail]=a[r]-a[r-d];q2[tail]=r;
        while (a[r]-a[l-1]-q1[head]>p)
        {
            if (head<=tail&&q2[head]==l+d-1) head++;
            l++;
        }
        ans=max(ans,r-l+1);
    }
    printf("%d",ans);
    return 0;
}

转载请注明:CodingBlog » bzoj 4385: [POI2015]Wilcze doły 单调队列

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情