洛谷 P3594 分析（别看）

科技起源

2026-07-07 14:35:55

发布于：河北

4阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：求一个最大长度

1.2 题目背景、允许、禁止与限制

背景：有一个长度为 $n$ 个数的序列 $a$
允许：选择其中一段长度不超过 $d$ 的区间，将其中所有元素清空为 $0$ ，最后找到一段最长的区间，使得区间总和不超过 $p$
禁止：
限制：只能进行一次操作

1.3 题目数据范围与猜测

$1 \le d,n \le 2\times10^6 \longrightarrow O(n)$

1.4 一句话概括题意

有一个序列，可以选择一次其中一段长度不超过 $d$ 的区间，将其中所有元素清空为 $0$ ，最后找到一段最长的区间，使得区间总和不超过 $p$

2 题目破题推导

注：以下六种方法都可以考虑一下

2.1 大拆小、小组大

2.2 正向思维转逆向思维，逆向思维转正向思维

既然因为最终区间总和不超过 $p$ ，又想找到最长的区间，因此一定需要先减去“序列中长度为 $d$ 的最长最大连续区间”

2.3 以终为始、以始为终

以终为始：最终答案是最长区间长度，我们不断向右拓展右端 r，记录当前最长合法长度；
以始为终：区间不合法时，只能向右移动左端点 l 缩小区间。

2.4 数学

什么情况下这段区间是合法的：当 $now(当前区间总和)-最大的t(这里的t_i代表以i为结尾，往前延伸d个元素的区间总和) \le p$

2.5 分情况考虑

2.6 手动推导

2.7 边界测试

3 模型匹配

提取关键词：
最长连续子数组且大小固定，是双指针滑动窗口
窗口内动态求区间最大值，是单调递减队列
快速求区间和，是前缀和
匹配标准模型：双指针 + 单调队列维护区间最值，经典线性滑动窗口极值问题。

4 具体方案

前面输入，维护sum和t都好说，主要是如何快速查找最大的t？标准单调队列模板

5 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 2e6 + 10;
int a[N];
int s[N], t[N];// t[i]表示以i为结尾的长度为d的子区间和
int now, mx;
int n, p, d;
int q[N], head = 1, tail = 0;
int l = 1, r;

signed main(){
	
	cin >> n >> p >> d;
	for (int i = 1;i <= n;i++){
		cin >> a[i];
		s[i] = s[i - 1] + a[i];
	} 
	for (int i = d;i <= n;i++){
		t[i] = s[i] - s[i - d + 1 - 1];
	}
	mx = d;// 初始默认最长区间长度至少为d(因为mx可以==p，而p >= 0)
	now = s[d];// 滑动窗口里的数字之和（刚开始默认前d项）
	q[++tail] = d;
	for (int r = d + 1;r <= n;r++){
		now += a[r];
		while(head <= tail && t[q[tail]] <= t[r]){
			tail--;
		}
		q[++tail] = r;
		while(now - t[q[head]] > p){
			if (q[head] < l + d){
				head++;
			}
			now -= a[l++];
		}
		mx = max(mx, r - l + 1);
	}
	cout << mx;
	
	return 0;
}