瑞士轮
2023-07-26 09:38:10
发布于：河北
6阅读
0回复
0点赞
由于每次比赛完都要通过得分和编号来进行排序，但是要比赛 r 次，用快速排序也比较慢，这个时候，可以想到每次比赛之后，得到的两个数组都是有序的，因此可以使用归并排序的 merge 操作，使得排序时候由 O(nlgn) 优化到 O(n)。
这里我们使用结构体，保存每个选手的编号，得分，能力，一开始通过编号和得分排序。
然后每轮比赛，让相邻的两个选手进行比较，这里比较就需要使用能力比较，然后胜利者进行得分，把胜利者和败者分别放在两个数组里，这样能保证两个数组都是有序的，就可以使用 merge 函数进行合并有序数组，优化排序时间，然后进行下一轮比赛。
merge 函数中比较是通过得分进行比较的，注意区分。
#include <iostream>
#include <algorithm>
using namespace std;
struct data {
int idx, g, pow;
} a[200010], win[200010], lose[200010];
bool cmp(data x, data y) {
if (x.g == y.g)
return x.idx < y.idx;
else
return x.g > y.g;
}
bool powcmp(data x, data y) {
return x.pow > y.pow;
}
void merge(int r1, int r2) {
int i = 1, j = 1, t = 1;
while (i <= r1 && j <= r2) {
if (cmp(win[i], lose[j]))
a[t++] = win[i++];
else
a[t++] = lose[j++];
}
while (i <= r1)
a[t++] = win[i++];
while (j <= r2)
a[t++] = lose[j++];
}
int main() {
int n, r, q, x;
cin >> n >> r >> q;
for (int i = 1; i <= 2 * n; i++) {
cin >> x;
a[i].g = x;
a[i].idx = i;
}
for (int i = 1; i <= 2 * n; i++) {
cin >> x;
a[i].pow = x;
}
sort(a + 1, a + 1 + 2 * n, cmp);
while (r--) {
int t1 = 1, t2 = 1;
for (int i = 1; i <= 2 * n; i += 2) {
if (powcmp(a[i], a[i + 1])) {
a[i].g++;
win[t1++] = a[i], lose[t2++] = a[i + 1];
} else {
a[i + 1].g++;
win[t1++] = a[i + 1], lose[t2++] = a[i];
}
}
merge(t1 - 1, t2 - 1);
}
cout << a[q].idx;
return 0;
}
这里空空如也
有帮助，赞一个