题目描述

难度分:$1600$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$、$m(1 \leq m \leq n)$、$low(1 \leq low \leq 10^9)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

你需要把数组$a$分成$m+1$段，选择其中一段留给自己，其余$m$段的元素和都必须$\geq low$。

输出留给自己的那段子数组（可以为空）的元素和的最大值。如果无法做到，输出$-1$。

输入样例

7
6 2 1
1 1 10 1 1 10
6 2 2
1 1 10 1 1 10
6 2 3
1 1 10 1 1 10
6 2 10
1 1 10 1 1 10
6 2 11
1 1 10 1 1 10
6 2 12
1 1 10 1 1 10
6 2 12
1 1 1 1 10 10

输出样例

22
12
2
2
2
0
-1

算法

双指针

由于$a$数组中都是正数，所以累加和是存在单调性的。可以先做一个预处理：

1. 正序遍历$i \in [1,n]$，同时维护前缀和$sum$，只要$sum \geq low$成立，$i$就可以作为一个段的结尾，追加到$pre$数组中。
2. 同理、、倒序遍历$i \in [1,n]$，同时维护后缀和$sum$，只要$sum \geq low$成立，$i$就可以作为一个段的结尾，追加到$suf$数组中。

为了方便，可以在最开始给$pre$加一个哨兵$0$，给$suf$加一个哨兵$n+1$。接下来继续遍历$i \in [1,n]$，看$pre$中有多少个下标满足$\lt i$。假设有$l$个下标，则$i$的左边可以分出来$l$个段，$i$的右边也就需要$r=m-l$个段。此时自己那一段的累加和就是$\Sigma_{i \in (pre[l],suf[r])a[i]}$，预处理出来一个前缀和数组就可以$O(1)$求得，维护这个累加和的最大值就能得到最终答案。

根据$a$数组累加和的单调性，随着$i$的右移，$l$的位置只会越来越右，而不会回退，所以这个过程是$O(n)$的。

复杂度分析

时间复杂度

预处理出$pre$、$suf$以及$a$的前缀和数组$s$的时间复杂度都是$O(n)$。之后双指针遍历$i$和$l$的时间复杂度也是$O(n)$，所以整个算法的时间复杂度就是$O(n)$。

空间复杂度

空间消耗就是$pre$、$suf$、$s$三个数组，都是线性空间。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
int T, n, m, low, a[N];
LL s[N];

void solve() {
    vector<int> pre, suf;
    pre.push_back(0);
    LL sum = 0;
    for(int i = 1; i <= n; i++) {
        sum += a[i];
        if(sum >= low) {
            pre.push_back(i);
            sum = 0;
        }
    }
    if(pre.size() < m) {
        puts("-1");
        return;
    }
    sum = 0;
    suf.push_back(n + 1);
    for(int i = n; i >= 1; i--) {
        sum += a[i];
        if(sum >= low) {
            suf.push_back(i);
            sum = 0;
        }
    }
    LL ans = -1;
    for(int i = 1, l = 0; i <= n; i++) {
        while(l < pre.size() && pre[l] < i) l++;
        int lcnt = l - 1;      // i的左边可以凑lcnt个和不小于low的段
        int rcnt = max(m - lcnt, 0);           // 右边就必须有rcnt个
        int tot = suf.size();
        if(rcnt < suf.size()) {
            int low = pre[lcnt], high = suf[rcnt];
            if(low < high) ans = max(ans, s[high - 1] - s[low]);
        }
    }
    printf("%lld\n", ans);
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d%d", &n, &m, &low);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            s[i] = s[i - 1] + a[i];
        }
        solve();
    }
    return 0;
}