题目描述

难度:[蓝]提高+/省选-

输入$n(1 \leq n \leq 2 \times 10^6)$，$p(0 \leq p \leq 1e16)$，$d(1 \leq d \leq n)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

你可以选择一个长度不超过$d$的连续子数组，把其中的元素都变成$0$。该操作至多执行一次。

输出最长连续子数组的长度，满足子数组元素和不超过$p$。

输入样例

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

输出样例

5

算法

二分答案+单调队列优化DP

这个题是个很综合的题，可以拆分成很多个知识点，每个都不难，但是揉在一起还是很有难度的。

二分答案整体框架

首先可以发现单调性，如果一个子数组$[l,r]$可以在删除一段长度不超过$d$的元素后达成$\Sigma_{i=l}^{r}a[i] \leq p$，那更短的数组肯定也能达成，因为数组中的元素都为正，更少的元素肯定累加和会更小。对于某个给定的子数组长度$w$，滑动窗口检查所有子数组：

1. 如果子数组$[l,l+w-1]$中长度不超过$d$的最大子段和不小于$\Sigma_{i=l}^{l+w-1}a[i]-p$，那说明$[l,l+w-1]$删除这段子数组后累加和肯定不会超过$p$。长度$w$符合要求，记录答案往右搜索长度，看能不能更大。
2. 如果没有任何一个长度为$w$的子数组满足上面一条，那$w$就给得太大了，应该往左搜索。

根据以上分析，我们发现需要预处理出长度不超过$d$的最大子段和，用动态规划来求解。先预处理出一个前缀和数组$s$，其中$s[i]=\Sigma_{j=1}^{i}a[j]$。

状态定义

$dp[i]$表示以$a[i]$结尾，长度不超过$d$的最大子段和。

状态转移

当遍历到$a[i]$时，前缀和为$s[i]$，需要找到一个$j \in [i-d,i)$，使得$s[i]-s[j]$最大，状态转移方程为$dp[i]=s[i]-min_{j \in [i-d,i)}s[j]$，发现是个滑动窗口求最值的问题，可以利用单调队列来优化状态转移。

二分答案$check$

求出$dp$数组后，在二分答案的$check$中，对于某个窗口长度$w$，当遍历到右端点$a[r]$时，求$[l+d-1,r]$（其中$l=r-d+1$，为区间左端点）上的$dp$最大值，这样就能得到子数组$[l,r]$内长度不超过$d$的最大子段和。又是一个滑动窗口求最值问题，利用单调队列来优化即可。

复杂度分析

时间复杂度

二分的时间复杂度为$O(log_2n)$，单调队列优化DP的时间复杂度为$O(n)$。因此，算法整体的时间复杂度为$O(nlog_2n)$。

空间复杂度

空间瓶颈在于单调队列的消耗，最差情况下队列会进入$O(n)$级别数量的元素，额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>

using namespace std;
typedef long long LL;

const int N = 2000010;
int n, d, a[N];
LL p, s[N], dp[N];

LL windowSum(int l, int r) {
    return s[r] - (l >= 1? s[l - 1]: 0);
}

bool check(int w) {
    // 滑动窗口求最大值
    deque<int> q;
    for(int r = 1; r < w; r++) {
        int l = r - w + 1;
        while(!q.empty() && q.front() < l + d - 1) q.pop_front();
        while(!q.empty() && dp[q.back()] <= dp[r]) q.pop_back();
        q.push_back(r);
    }
    for(int r = w; r <= n; r++) {
        int l = r - w + 1;
        LL sum = windowSum(l, r), delta = sum - p;
        if(delta <= 0) return true;
        while(!q.empty() && q.front() < l + d - 1) q.pop_front();
        while(!q.empty() && dp[q.back()] <= dp[r]) q.pop_back();
        q.push_back(r);
        // 检查结尾在[l+d-1,r]内长度不超过d的最大子段和是不是超过delta
        if(dp[q.front()] >= delta) return true;
    }
    return false;
}

int main() {
    scanf("%d%lld%d", &n, &p, &d);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];
    }
    // 长度不超过d的最大子段和
    deque<int> q;
    q.push_back(0);
    for(int r = 1; r <= n; r++) {
        while(!q.empty() && r - q.front() > d) q.pop_front();
        dp[r] = max(dp[r], s[r] - s[q.front()]);
        while(!q.empty() && s[q.back()] >= s[r]) q.pop_back();
        q.push_back(r);
    }
    // 二分答案
    int l = 1, r = n;
    while(l < r) {
        int mid = l + r + 1 >> 1;
        if(check(mid)) {
            l = mid;
        }else {
            r = mid - 1;
        }
    }
    printf("%d\n", r);
    return 0;
}