NOIP2011 普及组【瑞士轮】题解（AC）

》》》点我查看「视频」详解》》》

AC_Code

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 2e5 + 10;

int n, r, q;
struct Node
{
	int s, w, id;
	bool operator< (const Node &t) const 
	{
		if (s != t.s)
			return s > t.s;
		return id < t.id;
	}
}a[N], b[N], c[N];

int main()
{
	cin >> n >> r >> q;
	n <<= 1;
	
	for (int i = 1; i <= n; ++ i )
		cin >> a[i].s;
	for (int i = 1; i <= n; ++ i )
		cin >> a[i].w, a[i].id = i;
	
	sort(a + 1, a + n + 1);
	
	while (r -- )
	{
		for (int i = 1; i <= n; i += 2)
			if (a[i].w > a[i + 1].w)
			{
				a[i].s ++;
				b[i + 1 >> 1] = a[i];
				c[i + 1 >> 1] = a[i + 1];
			}
			else
			{
				a[i + 1].s ++;
				b[i + 1 >> 1] = a[i + 1];
				c[i + 1 >> 1] = a[i];
			}
				
		int i = 1, j = 1, k = 1;
		while (i <= n / 2 && j <= n / 2)
			if (b[i] < c[j])
				a[k ++] = b[i ++];
			else
				a[k ++] = c[j ++];
		while (i <= n / 2)
			a[k ++] = b[i ++];
		while (j <= n / 2)
			a[k ++] = c[j ++];
	}
	
	cout << a[q].id << endl;
	
	return 0;
}

》》》点我查看「视频」详解》》》