P1309 瑞士轮

[永遠の記憶 ~ Precious Memories]施工D11

2020.3.19

转载自luogu

P1309 瑞士轮

Noip2011 T3

题目传送门

11年复赛的第三题一改往常T3的忧郁与黑暗（笑）
这次难得给了一道归并
平时的dp还比较亲民
还可以随便骗部分分
这次的归并
说实话，
要不是我学过，我都不太想动这题
但是其实也忘得差不多了
我对不起教练
今天还是教练生日

这道题，是一道归并

没背模板的同学们，罚打绀珠传lunatic 100遍

不过好像我就没背下来

其实就是一个很裸的归并，每次比较时
分成两队，然后继续往下分 –> O(n)
每次循环merge一次 –> O(logn)
然后这么算下来时间复杂度为 –> O(nlogn)
应该是不会T的

那么我们就可以写出最后的代码了

因为实在记不得归并了，所以就用STL了。。。
代码如下:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5;
int n, r, q;
struct node {
	int s, w;
	int rank;
	bool operator<(const node &n) {
		if (n.s != s) return s > n.s;
		return rank < n.rank;
	}
} p[maxn*2], A[maxn*2], B[maxn*2];

int main() {
	scanf("%d%d%d", &n, &r, &q);
	for (int i = 1; i <= 2*n; ++i) {
		scanf("%d", &p[i].s);
		p[i].rank = i;
	}
	for (int i = 1; i <= 2*n; ++i) {
		scanf("%d", &p[i].w);
	}
	sort(p + 1, p + 1 + n*2);
	
	while (r--) {
		for (int i = 1; i <= n; ++i) {
			if (p[2 * i - 1].w < p[2 * i].w) {
				p[2 * i].s++;
				B[i] = p[2 * i - 1];
				A[i] = p[2 * i];
			}
			else {
				p[2 * i - 1].s++;
				B[i] = p[2 * i];
				A[i] = p[2 * i - 1];
			}
		}
		merge(B + 1, B + 1 + n, A + 1, A + 1 + n, p + 1);
	}
	cout << p[q].rank << endl;
	return 0;
}

还是对我们这种记性不好的人的有点不友好
还是dp大法好
不说了
去练绀珠传了(逃