CF1552B Running for Gold

Crazy_boy's Blog / 2024-01-21 / 原文

CF1552B Running for Gold

题目传送门

题面

奥运比赛刚刚开始，Federico 便十分渴望观看比赛。

有 $n$ 个选手参加了马拉松比赛，从 $1$ 到 $n$ 依次编号。她们都参加了 $5$ 项比赛，比赛从 $1$ 到 $5$ 编号。

现在有一个二维的数组 $r_{i,j}(1 \leq i \leq n,1 \leq j \leq 5)$，表示选手 $i$ 在比赛 $j$ 中排名第 $r_{i,j}$ 名。

Federico 认为选手 $u$ 优于选手 $v$，当且仅当，$u$ 在至少 $3$ 个项目中战胜了 $v$（即排名在 $v$ 前）。

Federico 认为选手 $x$ 能够获得金牌当且仅当 $x$ 可以战胜其它所有选手。

给定 $r_{i,j}$，求是否有一名选手可以获得金牌。

思路

题目中仅要求输出一名即可，所以为了保证尽可能快的锁定这一名，可以先对每一个选手进行一个排序，按照一个人能否战胜另一个人为比较条件

虽然获胜不具备传递性（即A胜B，B胜C，但是A不一定胜C），但是如果按照上述方法进行排序，那么第一个人一定是最有可能获得金牌的，而不是一定能获得金牌

所以，当排完序后，再对第一个人进行一个检查，看看他能否战胜其余所有人即可

代码

我们可以建两个数组，一个存储比赛结果($a$)，另一个负责索引($r$)，即$a_{i,j}$表示选手$i$在比赛$j$中排名第$r_{i,j}$名，而$r_i$是排序数组，表示当前位于第$i$个位置的运动员在$a$数组中的编号

所以最后对$r$进行排序，再用cmp进行判断，看看两个$r$数组中对应的两个运动员能否战胜彼此，依据就是$a$数组（具体实现可以看代码）

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn=5e4+10;
int a[Maxn][10];
int r[Maxn];
int flag,n;
bool cmp(int x,int y)
{
    int num=0;
    for(int i=1;i<=5;i++) num+=(a[x][i]<a[y][i]);
    return num>=3;
}
void run()
{
    cin>>n;flag=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=5;j++)
        {
            cin>>a[i][j];
            r[i]=i;
        }
    sort(r+1,r+n+1,cmp);
    for(int i=2;i<=n && flag;i++)
        if(!cmp(r[1],r[i])) flag=0;
    cout<<(flag?r[1]:-1)<<endl;
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--) run();
    system("echo. & pause");
    return 0;
}