题解 | #回家。。。回家#

题目大意

博士会路过n个沼泽，他可以跳过不超过k个，但每次跳过都会使得后面所有的沼泽伤害+1。我们来考虑这个问题，首先我们明确一点，无论何时，跳过沼泽总是对当前是更有利的，所以我们可以只要有跳过的机会就去跳过，但是如果后面存在一个沼泽，跳过它可以为我减少更多的伤害，我们可以执行“反悔操作”，从前面找一个对我减伤最小的跳过操作然后撤销。那么要想获得最多的减伤，就要执行减伤前k大的跳越操作。
$\qquad$ 接下来我们考虑如何去量化每次跳越的“减伤”大小，设我前面已经执行了k次跳越操作，第i次执行的时候跳过的沼泽位置为 $l o c [i]$ ,当前的位置为x，设每个沼泽的伤害 $h u r t [i]$ ,那么我撤销这次操作给我带来的收益就是 $h u r t [x] - h u r t [l o c [i]] + x - l o c [i]$ ,整理后得到 $(h u r t [x] + x) - (h u r t [l o c [i]] + l o c [i])$ ,我们可以发现用当前跳越操作取代一个之前的跳越操作带来的减伤是 $(当前伤害值 + 当前下标) - (撤销的伤害值 + 撤销的下标)$ ，要想让减伤最大，我们就要跳过 $(伤害值 + 下标)$ 排前k大的沼泽

解题代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxm=2e5+7;
ll a[maxm];
struct Data{
    ll a,b,id,have;
}all[maxm];
//那么我们就看看在第i个位置完成一次跳越带来的收益是多少
//如果我剩余的跳越次数不一样，那么跳越带来是收益也是不一样的
//并且跳越可能会带来负收益
//反悔贪心？
//从前往后进行遍历，只要是正收益我就跳
//如果已经满了的看看撤销之前的跳越操作、执行这次的会不会带来更大的收益
//转移的话是减少了(最小的伤害值+下标)-(当前的伤害值+下标)，如果说这个数字越大，我们越应该跳过
//
void solve(){
    ll n,k;
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&all[i].a);
        all[i].b=all[i].a+i;
        all[i].id=i;
    }
    sort(all+1,all+n+1,[&](Data x,Data y){return x.b>y.b;});
    for(int i=1;i<=n;i++){
        if(i<=k) all[i].have=1;
        else all[i].have=0;
    }
    sort(all+1,all+n+1,[&](Data x,Data y){return x.id<y.id;});
    ll sum=0,cnt=0;
    for(int i=1;i<=n;i++){
        if(all[i].have==1){
            cnt++;
        }
        else{
            sum+=all[i].a+cnt;
        }
    }
    cout<<sum<<endl;
}
int main(){
    ll T;
    scanf("%lld",&T);
    while(T--) solve();
    return 0;
}