洛谷P1309 瑞士轮

发表于 | 更新于: | 分类于 ， ， | | 阅读数
字数统计: 935 | 阅读时长 ≈ 4

Description

$2\times N$名编号为 $1\sim 2N$ 的选手共进行$R$轮比赛。每轮比赛开始前，以及所有比赛结束后，都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。总分相同的，约定编号较小的选手排名靠前。

每轮比赛的对阵安排与该轮比赛开始前的排名有关：第1名和第2名、第3名和第4名、……、第$2K-1$名和第$2K$名、…… 、第$2N-1$名和第$2N$名，各进行一场比赛。每场比赛胜者得1分，负者得0分。也就是说除了首轮以外，其它轮比赛的安排均不能事先确定，而是要取决于选手在之前比赛中的表现。

现给定每个选手的初始分数及其实力值，试计算在R轮比赛过后，排名第Q的选手编号是多少。我们假设选手的实力值两两不同，且每场比赛中实力值较高的总能获胜。

Input

第一行是三个正整数$N,R,Q$每两个数之间用一个空格隔开，表示有$2\times N$名选手、R轮比赛，以及我们关心的名次Q。

第二行是$2\times N$个非负整数$s1,s_2,\dots,s{2N},$每两个数之间用一个空格隔开，其中$si$表示编号为i的选手的初始分数。 第三行是$2\times N$个正整数$w_1,w_2,\dots,w{2N}$每两个数之间用一个空格隔开，其中$w_i$表示编号为i的选手的实力值。

Output

一个整数，即R轮比赛结束后，排名第Q的选手的编号。

Sample Input

1
2
3
2 4 2 
7 6 6 7 
10 5 20 15

Sample Output

1
1

Analysis

每组比赛的胜者：赛前，总分是按降序排的；获胜后都得1分，仍是降序；

每组比赛的负者：赛前，总分是按降序排的；不得分，仍是降序。

先按初始分数排序，然后按分数高低两人一组比赛；

胜者入队A，负者入队B。这样A、B自身仍是有序的；

只需进行合并操作即可，合并操作的复杂度是O(n),而如果用快排其复杂度为O(nlogn)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <algorithm>
using namespace std;
int N, R, Q;
int W[200005];
struct node
{
	int s;
	int id;
};
node a[200005];
node A[100005];
node B[100005];
bool cmp(node x, node y)
{
	if (x.s != y.s)
		return x.s > y.s;
	else
		return x.id < y.id;
}
void merge()
{
	int i = 1, j = 1, k = 1;
	while (i <= N && j <= N)
	{
		if ((A[i].s > B[j].s) || (A[i].s == B[j].s&&A[i].id < B[j].id))
		{
			a[k].s = A[i].s;
			a[k++].id = A[i++].id;
		}
		else
		{
			a[k].s = B[j].s;
			a[k++].id = B[j++].id;
		}
	}
	while (i <= N)
	{
		a[k].s = A[i].s;
		a[k++].id = A[i++].id;
	}
	while (j <= N)
	{
		a[k].s = B[j].s;
		a[k++].id = B[j++].id;
	}
}
int main()
{
	cin >> N >> R >> Q;
	for (int i = 1; i <= 2 * N; i++)
	{
		cin >> a[i].s;
		a[i].id = i;
	}
	for (int i = 1; i <= 2 * N; i++)
	{
		cin >> W[i];
	}
	sort(a + 1, a + 1 + 2 * N, cmp);
	for (int i = 1; i <= R; i++)
	{
		int tt = 1;
		for (int j = 1; j < 2 * N; j += 2)
		{
			if (W[a[j].id] > W[a[j+1].id])
			{
				A[tt].s = a[j].s + 1;
				A[tt].id = a[j].id;
				B[tt].s = a[j + 1].s;
				B[tt].id = a[j + 1].id;
				tt++;
			}
			else
			{
				A[tt].s = a[j + 1].s + 1;
				A[tt].id = a[j + 1].id;
				B[tt].s = a[j].s;
				B[tt].id = a[j].id;
				tt++;
			}
		}
		merge();
	}
	cout << a[Q].id << endl;
	return 0;
}