analysis
这个题目我们可以考虑用贪心来做。
我们不难看出来,这个题目是要让我们推出这么个结论:花小钱,办大人。
整体贪心的思路就出来了,然后就是实现部分。
因为我们认识的人随便是谁都可以。所以我们如果要买肯定是买最便宜的。这个性质可以用小根堆来维护。同时我们还可以维护我们可能结交的人数 \(n - size_q\) 如果比这个人需要的人少直接白嫖不需要什么操作,如果不行就买下来这个人。
code time
原谅蒟蒻当时写的时候因为忘记怎么写小根堆了,所以多此一举写了个结构体。>_<
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rl register ll
#define x first
#define y second
typedef pair<ll, ll> pll;
const ll N = 2e5 +10;
ll n, ans;
pll a[N];
struct node
{
ll x;
bool operator <(const node &o) const
{
return x > o.x;
}
};
priority_queue<node> q;
int main()
{
// freopen("1.in", "r", stdin), freopen("1.out", "w", stdout);
scanf("%lld", &n);
for(rl i=0; i < n; ++ i) scanf("%lld%lld", &a[i].x, &a[i].y);
sort(a, a + n);
for(rl i=n - 1; i >= 0; -- i)
{
q.push({a[i].y});
if(a[i].x > n - q.size())
{
auto t = q.top();
ans += t.x;
q.pop();
}
}
printf("%lld", ans);
return 0;
}
标签:CF1251E1,Voting,CCO2017,ll,Easy,ans,rl,lld,define
From: https://www.cnblogs.com/carp-oier/p/17748680.html