NKOJ 3775 数列操作（单调队列+DP）

发表于 |
字数统计: 543字 | 阅读时长 ≈ 3min

P3775数列操作

问题描述

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

输入格式

第一行包含三个整数n,p,d(1<=d<=n<=300000，0<=p<=10^16)。
第二行包含n个正整数，依次表示序列中每个数wi。

输出格式

包含一行一个正整数，即修改后能找到的最长的符合条件的区间的长度。

样例输入

9 7 2
3 4 1 9 4 1 7 1 3

样例输出

5

由于要讨论区间和，所以先求出前缀和数组$Sum[i]$，现在如果我们选择以j结尾的一个区间，那么有$Sum[j]-Sum[i]-(Sum[x]-Sum[x-d])<=p，x-d>=i，x<=j$，
所求的区间就是$[i+1,j]$。那么我们需要找到满足条件的最小的i。
考虑用单调队列优化，由于$Sum$数组是单调递增的，因此用$l$记下当前讨论的区间的左端点，如果左端点不满足上述条件，那么右移，现在只需要找到当前区间中$(Sum[x]-Sum[x-d])$的最大值即可，这个用单调队列维护即可。然而我石乐志，用堆来维护。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<deque>
#include<queue>
#define ll long long
#define N 333333
using namespace std;
struct node{ll v,x;};
bool operator<(node a,node b)
{return a.v<b.v;}
priority_queue<node>Q;
deque<ll>P;
node tmp;
ll n,p,d,i,j,k,S[N],ans;
int main()
{
	scanf("%lld%lld%lld",&n,&p,&d);
	for(i=1;i<=n;i++)scanf("%lld",&k),S[i]=S[i-1]+k;
	for(i=0;i<d;i++)P.push_back(i);
	for(i=d;i<=n;i++)
	{
		tmp.v=S[i]-S[i-d];
		tmp.x=i-d;
		Q.push(tmp);
		P.push_back(i);
		while(P.size()&&p+S[P.front()]+Q.top().v<S[i])
		{
			P.pop_front();
			while(Q.size()&&Q.top().x<P.front())Q.pop();
		}
		ans=max(ans,i-P.front());
	}
	cout<<ans;
}