Skip to content

「POI2015」Wilcze doły

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

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

#输入格式

输入的第一行包含三个整数,分别代表 n,p,dn, p, d

第二行包含 nn 个整数,第 ii 个整数代表序列中第 ii 个数 wiw_i

#输出格式

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

#输入输出样例

样例输入 #1

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

样例输出 #1

5

#数据范围与约定

对于 100%100\% 的数据,1dn2×1061 \leq d \leq n \leq 2 \times 10^60p10160 \leq p \leq 10^{16}1wi1091 \leq w_i \leq 10^9

#思路

单调队列 + 双指针。

由题:

你有一次机会选中一段连续的长度不超过 dd 的区间,将里面所有数字全部修改为 00

可知答案的最小值为 dd,因为其区间和为 00,一定不大于 pp

如果有一个确定的区间 [l,r][l, r],显然删掉这个区间里长度不超过 dd 且和最大的子区间之后,区间和会最小。那么就有了一个 O(n3)O(n^3) 的算法:枚举 l,rl, r,选择其中和最大的长度为 dd 的区间,然后判断剩余元素的和是否 p\leq p

考虑优化,发现可以使用双指针算法。先令 r=d+1r = d + 1,然后从 11 开始向后查找,直到删去区间内长度为 dd 且和最大的子区间后剩余的区间和 p\leq p 时停止查找,此时将答案与 rl+1r - l + 1 取最大值即可。此时复杂度为 O(n2)O(n^2)

考虑继续优化,发现可以使用前缀和优化求和的复杂度。设 sis_i 表示 [1,i][1, i] 区间内所有元素的和,tit_i 表示 (id,i](i - d, i] 区间内所有元素的和。这样就可以省去了求和的时间,最终时间复杂度为 O(n)O(n)

#代码

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
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <deque>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 2e6 + 5;

int n, d, a[N], ans;
long long p, sum, s[N], t[N];
std::deque<int> q;

int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> n >> p >> d;

for (int i = 1; i <= n; i++) {
cin >> a[i];

s[i] = s[i - 1] + a[i];
}

for (int i = 1; i <= n; i++) {
t[i] = s[i] - s[i - d];
}

ans = d;
sum = s[d + 1];
q.push_back(d);

for (int l = 1, r = d + 1; r <= n; sum += a[++r]) {
while (!q.empty() && t[q.back()] <= t[r]) q.pop_back();
q.push_back(r);
while (sum - t[q.front()] > p) {
if (q.front() < l + d) q.pop_front();
sum -= a[l++];
}
ans = std::max(ans, r - l + 1);
}

cout << ans << endl;

return 0;
}