正经题解｜瑞士轮

【算法分析】

首先想到使用sort进行每一轮排序，而sort是二分的思想，时间复杂度为 $O(nlog_2n)$，在此次题中，每次需要更新的值都是相邻两个人变化后的分数，而相邻两个人的分数有时是不会改变位置的，sort则是每次全部修改，造成了浪费。

然后考虑归并，归并的思想是合并两个同序数组的线性方式，每次比较两个有序数组的值，谁更小则放到tmp数组里，指针加1，归并排序每次的操作只针对相邻区间，或者说合并时是对相邻几个区间的操作，所以这符合只需要修改相邻几个分数的排布状况的题意。即使和快排的复杂度相同，但是省掉了冗杂无用的操作，是一个极大的改良。

【参考代码】

#include <iostream>
#include <algorithm>
using namespace std;

int n, r, q;

struct node {
	int id;//编号 
	int s; //分数 
	int w; //实力值 
}p[200010], b[100010], c[100010]; //p为总序列，b为胜者序列，c为败者序列 

bool cmp(node x, node y) {
	if (x.s == y.s) return x.id < y.id;
	else return x.s > y.s;
}

void work() { //比较每一次比赛的胜负，胜者进入b数组，败者进入c数组 ，并将两个数组合并 
	int lb = 0, lc = 0, lp; //p,b,c数组的指针
	for (int i = 1; i < n * 2; i += 2) {
		if (p[i].w > p[i + 1].w) {
			p[i].s++;
			b[++lb] = p[i];
			c[++lc] = p[i + 1];
		}
		else {
			p[i + 1].s++;
			b[++lb] = p[i + 1];
			c[++lc] = p[i];
		}
	}
	//合并 
	lp = lb = lc = 1;
	while (lb <= n && lc <= n) {
		if (cmp(b[lb], c[lc])) p[lp++] = b[lb++]; //按照实力相同，编号小的在前面、实力不同，实力大的在前面的排序规则 
		else p[lp++] = c[lc++];
	}
	while (lb <= n) p[lp++] = b[lb++];
	while (lc <= n) p[lp++] = c[lc++];
}

int main() {
	cin >> n >> r >> q; //2*n位选手，r轮比赛，排名第q的选手 
	for (int i = 1; i <= n * 2; i++) {
		cin >> p[i].s;
		p[i].id = i;
	}
	for (int i = 1; i <= n * 2; i++) {
		cin >> p[i].w;
	}
	sort(p + 1, p + 1 + n * 2, cmp); //第一次为无序，将数组排序 
	for (int i = 1; i <= r; i++) {   //进行r轮比赛 
		work();
	}
	cout << p[q].id;
	return 0;
}

【时间复杂度】

$O(rn)$

【预计得分】

$100pts$