題意
https://vjudge.net/problem/CodeForces-1251E2
一共有 n 個選民，你可以付出 pi? 的代價讓第 i 個選民為你投票，或者，在為你投票的人數達到 mi? 時，他會主動為你投票而不用你付出任何代價，
問得到所有選民投票的最小代價，
思路
考慮貪心，對容易跟風的就跟風，對不容易跟風的就賄賂，所以對每個mi用vector插入相應的pi，然后從大到小遍歷vector（不易跟風的要花錢），對于每一個mi，把對應的p插入到小根堆，小根堆里的人默認是跟風的，設小根堆大小為sz，每一次我們假設前面的人都已經把票投給你了，現在只用判斷前面的人數n-sz是否大于等于當前的mi，如果是，則說明滿足條件；否則要賄賂費用最少的人，將他移出小根堆（他不再跟風了，而是花錢買了），
代碼
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
vector<ll> g[N];
int main()
{
std::ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=0; i<n; i++)
g[i].clear();
for(int i=1; i<=n; i++)
{
ll m,p;
cin>>m>>p;
g[m].push_back(p);
}
priority_queue<ll,vector<ll>,greater<ll> >pq;
int cnt=0;
ll ans=0;
for(int i=n-1; i>=0; i--)
{
int sz=g[i].size();
for(int j=0; j<sz; j++)
{
pq.push(g[i][j]);
}
while(n-pq.size()<i)
{
ans+=pq.top();
pq.pop();
}
}
cout<<ans<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/125554.html
標籤：其他