57 lines
1.1 KiB
C++
57 lines
1.1 KiB
C++
#include <iostream>
|
|
#include <vector>
|
|
#include <algorithm>
|
|
|
|
using namespace std;
|
|
|
|
// 找到 <= x 的最近可用时间
|
|
int findPos(vector<int>& parent, int x) {
|
|
if (x <= 0) return 0;
|
|
if (parent[x] == x) return x;
|
|
return parent[x] = findPos(parent, parent[x]);
|
|
}
|
|
|
|
int main() {
|
|
ios::sync_with_stdio(false);
|
|
cin.tie(nullptr);
|
|
|
|
int n;
|
|
cin >> n;
|
|
|
|
vector<pair<int,int>> jobs(n);
|
|
|
|
int maxd = 0;
|
|
for (int i = 0; i < n; i++) {
|
|
cin >> jobs[i].first >> jobs[i].second;
|
|
maxd = max(maxd, jobs[i].first);
|
|
}
|
|
|
|
// 按收益降序
|
|
sort(jobs.begin(), jobs.end(),
|
|
[](const pair<int,int>& a, const pair<int,int>& b) {
|
|
return a.second > b.second;
|
|
});
|
|
|
|
// 并查集初始化
|
|
vector<int> parent(maxd + 1);
|
|
for (int i = 0; i <= maxd; i++) {
|
|
parent[i] = i;
|
|
}
|
|
|
|
long long ans = 0;
|
|
|
|
for (auto &job : jobs) {
|
|
int d = job.first;
|
|
int p = job.second;
|
|
|
|
int pos = findPos(parent, d);
|
|
|
|
if (pos > 0) {
|
|
ans += p;
|
|
parent[pos] = findPos(parent, pos - 1);
|
|
}
|
|
}
|
|
|
|
cout << ans << "\n";
|
|
return 0;
|
|
} |