用双指针枚举答案区间，再用单调队列维护当前窗口内“长度恰好为 d 的子段最大和”，从而快速判断把哪一段清零后能否让总和不超过 p。
OJ: luogu
题目 ID: P3594
难度:提高+/省选-
标签:双指针单调队列前缀和优化
日期: 2026-06-21 06:31
题意
给定一个长度为 n 的正整数序列。
你可以选择至多一次，把某一段连续长度不超过 d 的区间全部改成 0。
要求找到最长的连续区间，使得在进行这次修改后，该区间内所有数的和不超过 p。
思路
先看一个适合小数据验证的暴力：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 55;
int n, d;
long long p;
int a[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// brute.cpp：枚举答案区间，再枚举要清零的那一段。
// 只适合小数据，用来帮助理解题意并辅助对拍。
cin >> n >> p >> d;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int ans = 0;
for (int left = 1; left <= n; left++) {
long long total = 0;
for (int right = left; right <= n; right++) {
total += a[right];
long long best_zero = 0;
for (int x = left; x <= right; x++) {
long long sum = 0;
for (int y = x; y <= right && y - x + 1 <= d; y++) {
sum += a[y];
if (sum > best_zero) {
best_zero = sum;
}
}
}
if (total - best_zero <= p) {
int len = right - left + 1;
if (len > ans) {
ans = len;
}
}
}
}
cout << ans << '\n';
return 0;
}暴力会枚举答案区间 [l,r]，然后再枚举这段区间里要清零的那一小段，求出能减掉的最大和。
显然这样太慢。
正解先固定一个候选答案区间 [left,right]。
设这段区间的总和是 sum(left,right)。
如果我们要让它在修改后不超过 p，本质上就是问：
在 [left,right] 里面，能不能找到一段长度不超过 d 的子区间，把它清零后使得：
sum(left,right) - removed <= p
因为所有数都为正数，所以在固定 [left,right] 的情况下，当然应该把“能清零的那一段”选成和最大的那一段。
又因为数都是正数，若长度允许不超过 d，那么最优一定会取到长度恰好为 d；
如果整个区间长度本来就不超过 d，那直接把整段清零即可。
于是问题变成：
- 用双指针维护一个当前窗口
[left,right] - 维护窗口总和
cur_sum - 维护窗口内所有“长度恰好为
d的子段和”的最大值
第三步可以用单调队列。
先预处理：
window_sum[i] = a[i] + a[i+1] + ... + a[i+d-1]
表示起点是 i、长度恰好为 d 的子段和。
当右端点向右移动到 right 时，新的长度为 d 的子段起点就是：
start = right-d+1
如果 start >= 1，就把 window_sum[start] 加入单调队列。
当左端点右移时，所有起点 < left 的长度为 d 子段都已经不完全落在当前窗口里了，需要从队头弹掉。
这样队头始终表示当前窗口内可以清零的、长度恰好为 d 的子段最大和。
于是判断当前窗口是否合法时：
- 如果窗口长度
<= d，可以整段清零，一定合法 - 否则看
cur_sum - max_d_segment <= p是否成立
若不合法，就不断右移左端点。
整个过程就是标准的双指针，每个下标和每个 window_sum 候选都只会进出队一次，总复杂度线性。
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000005;
int n, d;
long long p;
int a[MAXN];
long long prefix_sum[MAXN];
// window_sum[i]：长度恰好为 d、起点是 i 的连续段和。
long long window_sum[MAXN];
// 单调队列里存的是“长度为 d 的子段起点”。
int que[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> p >> d;
for (int i = 1; i <= n; i++) {
cin >> a[i];
prefix_sum[i] = prefix_sum[i - 1] + a[i];
}
// window_sum[i]：长度恰好为 d、起点是 i 的连续段的元素和。
if (d <= n) {
for (int i = 1; i + d - 1 <= n; i++) {
window_sum[i] = prefix_sum[i + d - 1] - prefix_sum[i - 1];
}
}
int ans = 0;
int left = 1;
long long cur_sum = 0;
int head = 1, tail = 0;
for (int right = 1; right <= n; right++) {
cur_sum += a[right];
// 新增一个“长度为 d 的子段”进入当前右端点的候选集合。
int start = right - d + 1;
if (start >= 1) {
while (head <= tail && window_sum[que[tail]] <= window_sum[start]) {
tail--;
}
que[++tail] = start;
}
// 只要当前窗口长度大于 d，并且“总和 - 最佳可清零的 d 段和”仍然超过 p，
// 就不断移动左端点。
while (left <= right) {
int len = right - left + 1;
if (len <= d) {
// 如果总长度本来就不超过 d，可以整段全部清零，一定合法。
break;
}
while (head <= tail && que[head] < left) {
head++;
}
if (head <= tail && cur_sum - window_sum[que[head]] <= p) {
break;
}
cur_sum -= a[left];
left++;
}
int len = right - left + 1;
if (len > ans) {
ans = len;
}
}
cout << ans << '\n';
return 0;
}复杂度
时间复杂度
总结
这题的关键是把“允许清零一段”转成“当前窗口里减去一个最大子段和”。
一旦看出这个最大子段和只需要维护长度恰好为 d 的连续段，并且随着双指针窗口移动，就可以自然地用单调队列完成维护。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
