考虑使用贪心。
对每个人按 \(m\) 从大到小排序,这样可以使后面跟风的人跟多,需要花费金币越少。
维护一个小根堆,从后往前枚举,每次将人的贿赂值入小根堆。
如果当前人民的跟风值大于在小根堆里的人数,就将答案加上堆顶元素,并将堆顶元素出堆。
最后输出答案。
注意易错点,每次要将堆清空。不会只有我才犯这种错误吧。
AC Code
#include<bits/stdc++.h>
using namespace std;
int n;
struct M{
int m,q;
}a[200005];
inline bool cmp(M x,M y){
return x.m<y.m;
}
priority_queue<int,vector<int>,greater<int> >q;
int main(){
int T;
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].m>>a[i].q;
}
while(q.size())q.pop();//清空堆
sort(a+1,a+n+1,cmp);
int cnt=0;
long long ans=0;
for(int i=n;i>=1;i--){
q.push(a[i].q);
if(a[i].m>n-q.size ())ans+=q.top(),q.pop();
}
cout<<ans<<endl;
}
return 0;
}