Educational CF Round 75 (Div. 2)___E2. Voting —— 思维

题目链接：点我啊╭(╯^╰)╮

题目大意：

    要获得 $n$ 个人所有的投票
    对于一个人，如果已经有 $m$ 个人投了票，则这个人可以免费投票
    或者花费 $p$ 让这个人投票
    求最小花费

解题思路：

    通过贪心选取，可以发现
    对于一个还未投票的人 $i$ ，最贪心的方式是在 $\ge m_i$ 的人里选一部分人
    让当前人数到达 $mi$ 后，让这个人免费投票

    我们不妨倒过来思考，反向枚举 $m$
    对于一个 $m_i$ ，我们肯定是已经让小于 $m_i$ 的人全都投了票
    然后将还未投票的（也就是 $\ge m_i$ 的人） $p$ 放到优先队列里
    在优先队列里选取一部分人，让当前人数到达 $m_i$

    因此，$q.size()$ 表示还未投票的，$n?q.size()$ 表示已经投票的人数
    从队列里贪心选取较小的 $p$，直到 $n?q.size()\ge m_i$

核心：反向思维

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
using pii = pair <ll,int>;
const int maxn = 2e5 + 5;
int T, n; 
vector <int> a[maxn];
priority_queue <int> q;int main() {scanf("%d", &T);while(T--){scanf("%d", &n);for(int i=0; i<=n; i++) a[i].clear();for(int i=1; i<=n; i++)	{int p, m;scanf("%d%d", &m, &p);a[m].push_back(p);}while(q.size()) q.pop();ll ans = 0;for(int i=n; ~i; i--){for(auto p : a[i]) q.push(-p);while(n - q.size() < i) {ans -= q.top();q.pop();}}printf("%lld\n", ans);}
}