题目描述

难度分:$1600$

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

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

从$a$中选一个长度至多为$m$的子序列$b$。设$b$的最后一个数在$a$中的下标为$i$，定义 $f(b)=sum(b)-i \times d$。（下标从$1$开始）你需要最大化$f(b)$。如果$b$是空的，那么$f(b)=0$。

注：子序列不一定连续。

输入样例

6
5 2 2
3 2 5 4 6
4 3 2
1 1 1 1
6 6 6
-82 45 1 -77 39 11
5 2 2
3 2 5 4 8
2 1 1
-1 2
6 3 2
-8 8 -2 -1 9 0

输出样例

2
0
60
3
0
7

算法

贪心

这个贪心还是比较好想的，从前往后考虑每个$a[i]$结尾的情况，这样就不重不漏了。如果$a[i]$是$b$的结尾元素，那它就会产生$a[i]-i \times d$的收益，前面最多还能选$m-1$个数，选择最大的$m-1$个正数就行了。如果正数不足$m-1$个，那就有多少选多少。

于是关键问题就在于当遍历到$i$位置时，如何维护好前面最大的$min(m-1,i-1)$个正数之和？用一个小根堆来存最大的$min(m-1,i-1)$个正数即可，小根堆的堆顶能被$a[i]$干掉时更新小根堆。

复杂度分析

时间复杂度

遍历$i \in [1,n]$时间复杂度为$O(n)$，对于每个$i$，会存在往小根堆中插入元素的情况，而小根堆中元素的最大数量是$O(m)$的，所以时间复杂度为$O(log_2m)$。因此，整个算法的时间复杂度为$O(nlog_2m)$。

空间复杂度

空间消耗就在于小根堆，其中最多存$m-1$个元素，因此额外空间复杂度为$O(m)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 200010;
int T, n, m, d, a[N];

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d%d", &n, &m, &d);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        LL gain = 0, ans = 0;
        priority_queue<int, vector<int>, greater<int>> heap;
        for(int i = 1; i <= n; i++) {
            // 假设一定要选a[i]
            LL delta = a[i] - 1LL * i * d;
            // 前面最多只能选m-1个数，选最大的m-1个
            ans = max(ans, gain + delta);
            if(a[i] > 0) {
                if(heap.size() < m - 1) {
                    heap.push(a[i]);
                    gain += a[i];
                }else {
                    if(!heap.empty() && heap.top() < a[i]) {
                        gain += a[i] - heap.top();
                        heap.pop();
                        heap.push(a[i]);
                    }
                }
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}