瑞士轮——结构体&&(快速排序 or 归并排序?)

题目链接：https://www.luogu.com.cn/problem/P1309

题意应该非常明确了(这里就不细讲了)：有2*N个人，首先根据成绩进行排序，相邻的两个人进行比赛，强的人成绩+1，输的人成绩不变，最后又根据成绩进行排序，进行r次操作，如果成绩相同，初始时序号在前的排前面，最后输出第q个人的序号。

思路:

1. 用快速排序和结构体，首先用结构体存数据，然后用STL库里面的sort函数，每次比较完更新就排一次序（具体实现看下列代码）。这样你会发现时间会爆炸，也就是TLE，那么为什么会出现这种情况呢？

2. 那就了解一下sort函数
   sort本质就是杂乱的二分（胡乱找中间点），左右两边俩俩交换，时间复杂度非常不稳定
   稳定的时候时间复杂度O(nlogn)左右，最坏的情况时间复杂度能到n的平方左右，这题你就能发现俩俩比较后不一定要交换，而快速排序是每次都交换，所以多了很多无用的操作，此题就卡了数据
   

3. 时间复杂度低的排序方法除了快速排序就是归并排序，归并排序时间复杂度稳定在O(nlogn),这题两两比较，赢得进A数组，输的进B数组，最后对A和B进行合并。
   为啥可以直接合并？初始状态已近是排好序，有序状态，相邻俩俩比较，A,B序列依旧都是有序的，所以可以直接合并,时间复杂度（n）
   例如：

如果对归并排序不熟悉的请移步这篇博客https://www.cnblogs.com/expect-999/p/17599008.html

快速排序sort（正确80%）

#define _CRT_SECURE_NO_WARNINGS 1

#define all(C) C.begin(),C.end()
#define S second
#define F first
#define PB push_back
#define mod 1000000007
#define import ios_base::sync_with_stdio(false);cin.tie(NULL)

#include <cstring>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>

using namespace std;
typedef long long ll;
const int N = 1e6 + 10;

int n,x,k;

struct stu
{
	int id;
	int grade;
	int ability;
}q[N];

bool cmp(stu a, stu b)
{
	if (a.grade != b.grade) return a.grade > b.grade;
	else return a.id < b.id;
}

signed main()
{

	cin >> n >> x >> k;

	for (int i = 1; i <=2*n; ++i)
	{
		q[i].id = i;
		cin >> q[i].grade;
	}

	for (int i = 1; i <= 2 * n; ++i) cin >> q[i].ability;

	sort(q+1, q + 2*n+1,cmp);

	while (x--)
	{
		for (int i = 1; i <= 2 * n; i+=2)
		{
			if (q[i].ability > q[i + 1].ability) q[i].grade++;
			else q[i + 1].grade++;
		}
		sort(q + 1, q + 2 * n + 1,cmp);
	}

	printf("%d", q[k].id);

	return 0;
}

归并排序(100%)

#define _CRT_SECURE_NO_WARNINGS 1

#define all(C) C.begin(),C.end()
#define S second
#define F first
#define PB push_back
#define mod 1000000007
#define import ios_base::sync_with_stdio(false);cin.tie(NULL)

#include <cstring>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>

using namespace std;

const int N = 2e5 + 10;

struct stu
{
	int id; //序号
	int grade; //成绩
}q[N],A[N],B[N];

int n, r, t;
int w[N]; // 能力

bool cmp(stu a, stu b)
{   //如果成绩不相等，成绩高的排前面，相等情况下序号小的排前面
	if (a.grade != b.grade) return a.grade > b.grade; 
	else return a.id < b.id;
}

void merge_sort()
{
	int i = 1, j = 1, k = 1;
	while (i <= n && j <= n) // A,B中数量都是n
	{
		if (A[i].grade > B[j].grade || (A[i].grade == B[j].grade && A[i].id < B[j].id) )
		{
			q[k].grade=A[i].grade;
			q[k++].id=A[i++].id;
		}
		else
		{
			q[k].grade = B[j].grade;
			q[k++].id = B[j++].id;
		}
	}

	while (i <= n) {
		q[k].grade = A[i].grade;
		q[k++].id = A[i++].id;
	}

	while(j<=n)
	{
		q[k].grade = B[j].grade;
		q[k++].id = B[j++].id;
	}
}


signed main()
{
	cin >> n >> r >> t ;
    //输入相应的数据
	for (int i = 1; i <= n * 2; ++i)
	{
		cin >> q[i].grade;
		q[i].id = i;
	}

	for (int i = 1; i <= n * 2; ++i) cin >> w[i];

	sort(q + 1, q + 2 * n + 1, cmp);

	while (r--)
	{
		int tt = 1; 
		for (int i = 1; i <= 2 * n; i += 2)
		{
			if (w[q[i].id] > w[q[i + 1].id])
			{
				A[tt].grade = q[i].grade + 1; 
				A[tt].id = q[i].id;
				B[tt].grade = q[i + 1].grade;
				B[tt].id = q[i + 1].id;
				tt++;
             //俩俩比较，进行成绩更新，分别进去A,B两个数组，胜者入A,败者入B
			}
			else
			{
				A[tt].grade = q[i+1].grade + 1;
				A[tt].id = q[i+1].id;
				B[tt].grade = q[i].grade;
				B[tt].id = q[i].id;
				tt++;
			}
		}
		merge_sort(); //归并排序
	}

	cout << q[t].id << endl;

	return 0;
}

本人蒟蒻，如有错误或不恰当的地方还望指点，如果对您有帮助，希望给个免费的点赞和关注，这对我很重要，感谢观看我的博客