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;
}