「POI2015」Wilcze doły

#题面

#题目描述

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

#输入格式

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

第二行包含 $n$ 个整数，第 $i$ 个整数代表序列中第 $i$ 个数 $w_i$。

#输出格式

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

#输入输出样例

样例输入 #1

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

样例输出 #1

5

#数据范围与约定

对于 $100\%$ 的数据，$1 \leq d \leq n \leq 2 \times 10^6$，$0 \leq p \leq 10^{16}$，$1 \leq w_i \leq 10^9$。

#思路

单调队列 + 双指针。

由题：

你有一次机会选中一段连续的长度不超过 $d$ 的区间，将里面所有数字全部修改为 $0$。

可知答案的最小值为 $d$，因为其区间和为 $0$，一定不大于 $p$。

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

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

考虑继续优化，发现可以使用前缀和优化求和的复杂度。设 $s_i$ 表示 $[1, i]$ 区间内所有元素的和，$t_i$ 表示 $(i - d, i]$ 区间内所有元素的和。这样就可以省去了求和的时间，最终时间复杂度为 $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;
}