题目描述
难度分:1600
输入T(≤104)表示T组数据。所有数据的n之和≤2×105。
每组数据输入n(1≤n≤2×105)、m(1≤m≤n)、low(1≤low≤109)和长为n的数组a(1≤a[i]≤109)。
你需要把数组a分成m+1段,选择其中一段留给自己,其余m段的元素和都必须≥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数组中都是正数,所以累加和是存在单调性的。可以先做一个预处理:
- 正序遍历i∈[1,n],同时维护前缀和sum,只要sum≥low成立,i就可以作为一个段的结尾,追加到pre数组中。
- 同理、、倒序遍历i∈[1,n],同时维护后缀和sum,只要sum≥low成立,i就可以作为一个段的结尾,追加到suf数组中。
为了方便,可以在最开始给pre加一个哨兵0,给suf加一个哨兵n+1。接下来继续遍历i∈[1,n],看pre中有多少个下标满足<i。假设有l个下标,则i的左边可以分出来l个段,i的右边也就需要r=m−l个段。此时自己那一段的累加和就是Σi∈(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;
}