|
已为你修改代码,望采纳。
|
#include <stdio.h>
#include <stdlib.h>
#define N 1007
struct zy {
int d, p, index;
};
struct zy zys[N];
int fa[N], sz[N];
// 比较函数,按照效益降序排序
int compare(const void *a, const void *b) {
struct zy *za = (struct zy *)a;
struct zy *zb = (struct zy *)b;
return (zb->p - za->p);
}
// 查找根节点
int find(int i) {
if (fa[i] == i) return i;
else {
fa[i] = find(fa[i]);
return fa[i];
}
}
// 合并节点
void merge(int x, int y) {
x = find(x), y = find(y);
sz[x] += sz[y];
fa[y] = x;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d %d", &zys[i].p, &zys[i].d);
zys[i].index = i;
}
// 按照效益降序排序
qsort(zys + 1, n, sizeof(struct zy), compare);
// 初始化并查集
for (int i = 1; i <= n; ++i) {
fa[i] = i;
sz[i] = 1;
}
// 选择任务
int ans[N], count = 0;
for (int i = 1; i <= n; ++i) {
if (find(zys[i].d) != 0) {
ans[count++] = zys[i].index;
merge(find(zys[i].d) - 1, find(zys[i].d));
}
}
// 对结果排序
qsort(ans, count, sizeof(int), compare);
// 输出结果
for (int i = 0; i < count; ++i) {
printf("%d", ans[i]);
if (i < count - 1) printf(" ");
}
return 0;
}