题目大意
如果 \(\texttt{Kevin}\) 想和第 \(i\) 个人交朋友，要么需要认识 \(a_i\) 个人，要么付出 \(b_i\) 的代价，他让你使 \(\texttt{Kevin}\) 与所有的人交朋友。
解题思路
如果想水到 \(15\) 分，也就是所有 \(b_i\) 都等于 \(1\) 的情况，那我们可以直接排个序，然后遍历一下每一个人，如果目前所认识的人数小于 \(a_i\)，那就付出 \(b_i\) 的代价，否则跳过。
排序部分代码：
bool cmp(node x, node y) {
if(x.a != y.a) {
return x.a < y.a;
}
return x.b < y.b;
}
处理部分代码：
for(int i = 1; i <= n; i++) {
if(know_cnt /*目前交的朋友的数量*/ < x[i].a) {
ans /*付出的最小代价*/ += x[i].b;
}
know_cnt++;
}
但我们的目标是 \(100\) 分，如果已经交了 \(i\) 个朋友，正在交 \(j\) 这个朋友，那么 \(j\) 的取值可以为 [0,n-1]，因为朋友关系是唯一的。而想要免费交到，就需要 \(j\) 的取值在 [a[i].x,n-1] 内。贪心选取最大值，将数组以 a[i].y 从大到小排序。
但是这样的话两重循环过不了，所以可以用优先队列稍加优化（即 priority_queue）。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
struct node {
int x, y;
} a[N];
int n;
int tot = 0;
int sum = 0, ans = 0, know_cnt = 0;
priority_queue<int, vector<int>, greater<int> > pq;
inline ll read() {
ll x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
inline void write(ll x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
inline bool cmp(node x, node y) {
return x.x > y.x;
}
int main() {
n = read();
for(int i = 1; i <= n; i++) {
int t1 = read(), t2 = read();
sum += t2;
if(t1 < n) {
a[++tot] = {t1, t2};
}
}
sort(a + 1, a + tot + 1, cmp);
for(int i = 1; i <= tot; i++) {
if(n - a[i].x > know_cnt) {
pq.push(a[i].y);
know_cnt++;
} else {
if(n - a[i].x == know_cnt && !pq.empty()) {
if(a[i].y > pq.top()) {
pq.pop();
pq.push(a[i].y);
}
}
}
}
while(!pq.empty()) {
ans += pq.top();
pq.pop();
}
write(sum - ans);
return 0;
}
``