题解 洛谷 P3594 [POI2015] WIL

1. 题面描述

题目链接

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

\(1\le d\le n\le 2\times10^6,0\le p\le10^{16},1\le w_i\le10^9\)，其中 \(w_i\) 表示第 \(i\) 个数的值。

2. 分析

如果没有修改操作，本题就是一个经典的双指针问题。

考虑修改。观察到序列中所有数均为正数，发现删除一个数一定不会让答案变得更劣，所以我们删除的区间的长度一定为 \(d\)。

那么对于一个区间 \([l,r]\)，发现我们删除的区间一定是区间 \([l,r]\) 中和最大的一个，这样会有更多的机会来扩展区间。

于是我们维护双指针 \(l,r\) 的同时维护区间 \([l,r]\) 中和最大的长为 \(d\) 的区间的和是多少，就可以通过上述值移动指针。

3. 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+5;

int n,p,d,head=1,tail=0;
int a[N];
ll sum[N],que[N];

inline ll val(int x) {return sum[x]-sum[x-d];}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>p>>d;
	for (int i=1; i<=n; i++) cin>>a[i], sum[i]=sum[i-1]+a[i];
	int ans=d;
	ll s=val(d);
	que[++tail]=d;
	for (int l=1,r=l+d; r<=n; r++) {
		while (head<=tail && val(que[tail])<=val(r)) tail--;
		que[++tail]=r; s+=a[r];
		while (l<=r && s-val(que[head])>p) {
			s-=a[l]; l++;
			while (head<=tail && que[head]-d+1<l) head++;
		}
		ans=max(ans,r-l+1);
	}
	cout<<ans<<'\n';
	return 0;
}

本文完。