AcWing 145. 超市
原题链接
简单
作者:
harrytsz
,
2021-04-27 22:34:24
,
所有人可见
,
阅读 370
#include<iostream>
#include <vector>
#include<algorithm>
using namespace std;
const int N = 10010;
int fa[N];
int n;
typedef pair<int, int> PII;
void init() {
for(int i = 0; i < N; i++) fa[i] = i;
}
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y) {
fa[find(x)] = find(y);
}
bool cmp(PII a, PII b) {
return a.first > b.first;
}
int main() {
while(cin >> n) {
int ans = 0;
vector<PII> pros(n);
for(int i = 0; i < n; i++) cin >> pros[i].first >> pros[i].second;
init();
sort(pros.begin(), pros.end(), cmp);
for(int i = 0; i < n; i++) {
int x = find(pros[i].second);
if(x) {
ans += pros[i].first;
merge(x, x-1);
}
}
cout << ans << endl;
}
return 0;
}