线上OJ:
一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid=1955 (opens in a new tab)
AcWing:https://www.acwing.com/problem/content/449/ (opens in a new tab)
洛谷:https://www.luogu.com.cn/problem/P1309 (opens in a new tab)
关键词句
“每轮比赛开始前,以及所有比赛结束后,都会按照总分从高到低对选手进行一次排名”
。这个句子告诉我们:
1、第一轮比赛之前需要先排一次序,不能直接上来就比;
2、每一轮比赛开始之前(排好序后),队伍是有序的
核心思想: 模拟 + 排序
本题可采用模拟,进行 r 轮后,输出排名第 q 的人即可
题解代码:
排序采用默认的快速排序先试一遍模拟
解法一、模拟+快速排序(不开O2情况下60%分,开了O2得80%分)
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, r, q;
struct Node
{
int s, w, id; // s为分数,w为实力值,id为选手编号
}a[N];
bool cmp(Node x, Node y)
{
if( x.s == y.s ) return x.id < y.id; // 如果分数相同,id 小的排在前面
else return x.s > y.s; // 否则。分数高的排在前面
}
int main()
{
scanf("%d %d %d", &n, &r, &q);
// 读入并初始化每个选手的分数、id,和实力值
for(int i = 1; i <= 2 * n; i++)
{
scanf("%d", &a[i].s);
a[i].id = i;
}
for(int i = 1; i <= 2 * n; i++) scanf("%d", &a[i].w);
sort(a + 1, a + 1 + 2 * n, cmp); // 按题意,每轮比赛前,先进行一次排序。故第一次比赛前的排序不能遗漏
while(r--) // 模拟 r 轮
{
for(int i = 1; i <= 2 * n; i += 2) // 每一次比赛两组人
a[i].w > a[i+1].w ? a[i].s++ : a[i+1].s++; // 如果第 i 个人的实力值更大,则第 i 个人的分数++;否则,第 i+1 个人的分数++
sort(a + 1, a + 1 + 2 * n, cmp); // 一轮结束后重新排序
}
printf("%d", a[q].id);
return 0;
}
以上方法在开了O2的情况下,只能过80%的测试点。