CF1862E

洛谷题目链接

Codeforces题目链接

分析

注意到娱乐度的减少只跟最后看的电影有关，所以我们可以枚举最后看的电影的位置，对于每个电影若其欢乐值为负数则肯定不会选，如果选的数量大于 $m$ 则把当前选的欢乐值最小的从答案中扣除，可以发现最后总的娱乐值为（设 $t_i$ 为选好的第 $i$ 场电影的时间）：

$$a_1?t_1\times d+a_2?(t_2?t_1)\times d+?a_m?(t_m?t_{m?1})\times d$$

把 $d$ 提取出来原式就变为了：

$$a_1+a_2+?a_m?(t_1+t_2?t_1+?t_m?t_{m?1})\times d$$

可以发现 $a_1+a_2+?a_m$ 即为 $a_1$ 到 $a_m$ 的总和（记为 $sum$），$t_1+t_2?t_1+?t_m?t_{m?1}$ 即为 $t_m$，所以最后原式即为：$sum?t_m\times d$。

最后用堆维护最小值，计算答案即可。

代码

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2 * 1e5 + 5;
int T, n, m, d, a[N];

signed main(){
	for(cin >> T; T; T --){
		priority_queue <int, vector <int>, greater <int> > q;
		cin >> n >> m >> d;
		int sum = 0, ans = 0;
		for(int i = 1; i <= n; i ++){
			cin >> a[i];
			if(a[i] > 0){
				q.push(a[i]);
				sum += a[i];
			}
			if(q.size() > m){
				sum -= q.top();
				q.pop();
			}
			ans = max(ans, sum - d * i);
		}
		cout << ans << "\n";
	}
	return 0;
}