Skip to content

洛谷 - P3594 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)

代码

#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;
}