CF1684D Traps

题目传送门

思路：

通过 vector 数组和 pair 存储陷阱所带来的最大的伤害以及它的位置，排序过后找到跳过 k 个陷阱的最优解，统计总伤害即可

个人认为把主代码放在函数里比较好看

AC CODE：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
inline int read(){//快读优化 
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}
inline void solve(){
    int n,k,a[200005],sum=0,cnt=0;
    n=read(),k=read();//读入 
    vector<pair<int,int> >v;//用 vector 来存储 
    for(int i=0;i<n;i++)a[i]=read();//读入 
    for(int i=0;i<n;i++)v.push_back({a[i]+i,i});//插入 v （ first：当前陷阱可能造成伤害的最大值；second：当前陷阱是第几个（由于不能改变穿过陷阱的顺序） 
    sort(v.begin(),v.end());//从小到大排序（默认用第一关键字排序） 
    while(k--){a[v.back().second]=0;v.pop_back();}//跳过造成伤害最多的 k 个陷阱，赋值为 0 
    for(int i=0;i<n;i++){
        if(a[i])sum+=a[i],sum+=cnt;//不跳过当前陷阱 
        else cnt++;//跳过当前陷阱 
    }
    cout<<sum<<endl;//输出答案 
}
signed main(){
    t=read();//读入 
    while(t--)solve();//调用函数 
    return 0;
}