瑞士轮

提议

2×N 名编号为 1∼2N1∼2N 的选手共进行R 轮比赛。第1 名和第2 名、第 3 名和第 4名、……、第2K−1名和第2K名、…… 、第2N−1名和第2N名，各进行一场比赛。每场比赛胜者得1分，负者得 0分,求排名第 Q 的选手的编号。

思路

运用结构体排序模拟比赛但会超时。

优化

在此基础上用归并排序。

代码

#include <bits/stdc++.h>
using namespace std;
struct p {
int s, f, b;
};
p a[2000005], a1[1000005], a2[1000005];
bool amns(p x1, p x2) {
if (x1.f == x2.f) return x1.b < x2.b;
else return x1.f > x2.f;
}
int main() {
//	freopen("ruishi.in","r",stdin);
//	freopen("ruishi.out","w",stdout);
int n, r, q;
cin >> n >> r >> q;

for (int i = 1; i <= 2 * n; i++) {
int x;
cin >> x;
a[i].b = i;
a[i].f = x;

}
for (int i = 1; i <= 2 * n; i++) {
int x;
cin >> x;
a[i].s = x;
}

int j1 = 0, j2 = 0;
sort(a + 1, a + 2 * n + 1, amns);
while (r--) {
j1 = 1;
j2 = 1;
for (int i = 1; i < 2 * n; i += 2) {
if (a[i].s > a[i + 1].s) {

a[i].f++;
a1[j1++] = a[i];
a2[j2++] = a[i + 1];
} else {
a[i + 1].f++;
a1[j1++] = a[i + 1];
a2[j2++] = a[i];
}
}
j1 = 1;
j2 = 1;
int js = 1;
while (j1 <= n and j2 <= n) {
if (amns(a1[j1], a2[j2])) a[js++] = a1[j1++];
else a[js++] = a2[j2++];
}
while (j1 <= n) a[js++] = a1[j1++];
while (j2 <= n) a[js++] = a2[j2++];


}
cout << a[q].b;
return 0;


}