CF1862E Kolya and Movie Theatre 题解

先注意到我们娱乐值损耗的多少只与最后一场电影有关系，所以假设最后一场电影看的下标为 \(k\)，那么最后就要减去 \(d \times k\)。

得出这个性质之后开个小根堆反悔贪心即可，首先 \(a_i<0\) 的没必要考虑，对于 \(a_i>0\) 的，如果还没到 \(m\) 场电影，我们就直接往里塞就可以，如果到了，我们就进行反悔操作，取出已选的贡献最小的那场电影，然后看看会不会更优，如果会的话就加进去。

算是反悔贪心板子题，时间复杂度 \(O(n\log n)\)。

然后就是一定要记得开 long long，吃了两发。

#include <cstdio>
#include <queue>
#include <algorithm>

typedef long long ll;

int t;
int n,m,d;
int a[200005];

void solve() {
	scanf("%d",&t);
	while(t--) {
		scanf("%d%d%d",&n,&m,&d);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		std::priority_queue<int> q;
		int tot=0;
		ll ans=0,sum=0;
		for(int i=1;i<=n;i++) {
			if(a[i]<0) continue;
			if(tot<m) {
				tot++;
				q.push(-a[i]);//大根堆每次存相反数作用就是小根堆
				sum+=a[i];
			} else if(-q.top()<a[i]) {//反悔操作
				sum+=q.top();
				q.pop();
				sum+=a[i];
				q.push(-a[i]);
			}
			ans=std::max(ans,sum-1ll*d*i);
		}
		printf("%lld\n",ans);
	}
}

int main() {
	solve();
	return 0;
}