并查集做法代码
/*
* Project: 0x41_并查集
* File Created:Saturday, January 9th 2021, 12:01:03 pm
* Author: Bug-Free
* Problem:AcWing 145. 超市
*/
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e4 + 10;
int n, fa[N];
pair<int, int> p[N];
int get(int x) {
if (x == fa[x]) {
return x;
}
return fa[x] = get(fa[x]); //路径压缩, 把这个集合中所有的 都指向根
}
void Supermarket() {
int d = 0, ans = 0;
for (int i = 1; i <= n; i++) {
cin >> p[i].first >> p[i].second;
d = max(d, p[i].second); //取得一个最晚过期时间
}
sort(p + 1,
p + n + 1); // 按照利润从小到大做一个排序, 后面倒着处理就好(从大到小)
for (int i = 0; i <= d; i++) { //起初每一天各自构成一个集合
fa[i] = i;
}
// 利用路径压缩, 可以快速找出从过期时间往前数第一个空闲的天数
for (int i = n; i; i--) { //从利润大的开始(从后往前)
int r = get(p[i].second); //获取利润最大的商品的过期日期
if (r) { //如果这个"位置"还没有被用掉
ans += p[i].first; //更新答案
//合并两个集合(r与r-1)-> 把这个"位置"指向他前一个"位置"
fa[r] = r - 1;
}
}
cout << ans << endl;
}
int main() {
while (cin >> n) {
Supermarket();
}
return 0;
}
录入p[i]数据那里,i的下标从0开始,后面排序也从p到p + n,为什么结果会错,从1开始就能过
改为下标从0开始也能过,你可能忘了下面的for循环从后往前枚举,i就要从n-1到0
合并集合为什么不是fa[r]=get(r-1)
因为下次再访问到这个第r-1天时,会先给它get路径压缩一下,然后进行之后的操作
感谢
并查集推荐用 wzc 大佬的模板,感觉挺不错的:https://www.acwing.com/file_system/file/content/whole/index/content/1382246/
b( ̄▽ ̄)d 好