( 1 ≤ t ≤ 2⋅10^5 )
一共有 n ( 1≤n≤2⋅10^5 ) 个选民，你可以付出 pi? ( 1 ≤ pi ?≤ 10^9 ,0 ≤ mi ?< n ).的代价让第 i 个选民为你投票，
或者，在为你投票的人数达到 mi? 时，他会主动为你投票而不用你付出任何代价。
问得到所有选民投票的最小代价。
luogu大佬题解：
先分层次，0-n-1层的选择的时候肯定不退
就是假设前面的都选，那个我这一层以及之后，最少选多少个，（贪心）
小根堆维护这一层和之后的最优选择
最后到第0层，正好就是选完了
#include<cstdio> #include<cstdlib> #include<queue> #define ll long long using namespace std; int n; const int N=2e5+3; vector <ll> g[N]; priority_queue <ll ,vector <ll> ,greater <ll> > q; int main() { int T; scanf("%d",&T); while(T--) { //input scanf("%d",&n); for(int i=0;i<=n;i++) g[i].clear() ; int x; ll y,ans=0; for(int i=1;i<=n;i++) { scanf("%d%lld",&x,&y); g[x].push_back(y) ; } //work while(!q.empty() ) q.pop() ; for(int i=n-1;i>=0;i--) { int sz=g[i].size() ; for(int j=0;j<sz;j++) q.push(g[i][j] ); int mn=n-i; sz=q.size() ; while(sz-- >mn) { ans+=q.top() ; q.pop() ; } } //output printf("%lld\n",ans); } return 0; }
原文：https://www.cnblogs.com/xwww666666/p/11796216.html