书上p195讲的很详细。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pii pair<int, int>
const int N = 1e4 + 100;
int fa[N], n, ans;
pii a[N];
int get(int x) { return fa[x] == x ? x : fa[x] = get(fa[x]); } //路径压缩
void merge(int x, int y) { fa[get(x)] = get(y); }
bool cmp(pii a, pii b) { return a.first > b.first; }
int main()
{
ios::sync_with_stdio(false);
while (cin >> n)
{
ans = 0;
for (int i = 0; i < n; i++)
cin >> a[i].first >> a[i].second;
for (int i = 0; i < N; i++)
fa[i] = i;
sort(a, a + n, cmp);//按利润降序
for (int i = 0; i < n; i++)
{
int x = get(a[i].second);
if (x)//如果天数还有剩余
{
ans += a[i].first;
merge(x, x - 1);//x为x-1的根
}
}
cout << ans << endl;
}
return 0;
}
哪本书
算法竞赛进阶指南
int x = get(a[i].second);
if (x)//如果天数还有剩余
{
ans += a[i].first;
merge(x, x - 1);//x为x-1的根
}
这里看不懂,我本来的做法是把就是天数从小到大排序,然后快过期的先卖,如果存在天数相同,那么就去相同天数中的最大值,然后把输入的数据加起来就行了