CF1552B Running for Gold
知识点：思维、证明
题目
The Olympic Games have just started and Federico is eager to watch the marathon race.
There will be n athletes, numbered from 1 to n, competing in the marathon, and all of them have taken part in 5 important marathons, numbered from 1 to 5, in the past. For each 1≤i≤n and 1≤j≤5, Federico remembers that athlete i ranked ri,j-th in marathon j (e.g., r2,4=3 means that athlete 2 was third in marathon 4).
Federico considers athlete x superior to athlete y if athlete x ranked better than athlete y in at least 3 past marathons, i.e., rx,j<ry,j for at least 3 distinct values of j.
Federico believes that an athlete is likely to get the gold medal at the Olympics if he is superior to all other athletes.
Find any athlete who is likely to get the gold medal (that is, an athlete who is superior to all other athletes), or determine that there is no such athlete.
输入
The first line contains a single integer t (1≤t≤1000) — the number of test cases. Then t test cases follow.
The first line of each test case contains a single integer n (1≤n≤50000) — the number of athletes.
Then n lines follow, each describing the ranking positions of one athlete.
The i-th of these lines contains the 5 integers ri,1,ri,2,ri,3,ri,4,ri,5 (1≤ri,j≤50000) — the ranking positions of athlete i in the past 5 marathons. It is guaranteed that, in each of the 5 past marathons, the n athletes have distinct ranking positions, i.e., for each 1≤j≤5, the n values r1,j,r2,j,…,rn,j are distinct.
It is guaranteed that the sum of n over all test cases does not exceed 50000.
输出
For each test case, print a single integer — the number of an athlete who is likely to get the gold medal (that is, an athlete who is superior to all other athletes). If there are no such athletes, print −1. If there is more than such one athlete, print any of them.
样例
输入
4
1
50000 1 50000 50000 50000
3
10 10 20 30 30
20 20 30 10 10
30 30 10 20 20
3
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
6
9 5 3 7 1
7 4 1 6 8
5 6 7 3 2
6 7 8 8 6
4 2 2 4 5
8 3 6 9 4
输出
1
-1
1
5
提示
Explanation of the first test case: There is only one athlete, therefore he is superior to everyone else (since there is no one else), and thus he is likely to get the gold medal.
Explanation of the second test case: There are n=3 athletes.
Athlete 1 is superior to athlete 2. Indeed athlete 1 ranks better than athlete 2 in the marathons 1, 2 and 3.
Athlete 2 is superior to athlete 3. Indeed athlete 2 ranks better than athlete 3 in the marathons 1, 2, 4 and 5.
Athlete 3 is superior to athlete 1. Indeed athlete 3 ranks better than athlete 1 in the marathons 3, 4 and 5.
Explanation of the third test case: There are n=3 athletes.
Athlete 1 is superior to athletes 2 and 3. Since he is superior to all other athletes, he is likely to get the gold medal.
Athlete 2 is superior to athlete 3.
Athlete 3 is not superior to any other athlete.
Explanation of the fourth test case: There are n=6 athletes.
Athlete 1 is superior to athletes 3, 4, 6.
Athlete 2 is superior to athletes 1, 4, 6.
Athlete 3 is superior to athletes 2, 4, 6.
Athlete 4 is not superior to any other athlete.
Athlete 5 is superior to athletes 1, 2, 3, 4, 6. Since he is superior to all other athletes, he is likely to get the gold medal.
Athlete 6 is only superior to athlete 4.
题意
n个人比5场比赛，每场比赛都是这n个人比，每场的排名不会有两个人相同，一个人有三场比赛排名小于另一个人表示这个人比另一个人强，求比除自己外任何一个人都强的人。
思路
如果认为a强于b且b强于c，则a强于c，即答案具有传递性，就有可能能蒙对题目。但实际上不存在传递性，样例2为反例，所以不能贪心。
按照题目要求，可以枚举所有人，对每一个人枚举除自己外所有人，如果这个人比除自己外任何一个人都强这个人就是答案。O（n^2）。
考虑到一个人比另一个人强并不意味着他比除自己外任何一个人都强，正向难以考虑。反向考虑，是本题最关键思维。然而只要一个人不比另一个人强，这个人不是答案。排除掉所有不比另一个人强的人，剩下的人中任意一个为答案。
证明如果一个人强于另一个人，另一个人必不强于另一个人。（这不是废话，如果比六场比赛就有可能出现双方互相强于对方）
若a强于b，则a至多有两个排名大于对应b的两个排名，则b至多有两个排名小于对应a的排名，即不可能存在三个排名小于对应a的排名，也就是必不强于另一个人。
证明比除自己外任何一个人都强的人只有一个。
若存在两个比除自己外任何一个人都强的人，比较这两个人a，b，结果必为a不强于b和b不强于a其一，显然矛盾。
注意到比较两个人a，b必能排除其一，a不强于b则a不是答案，而b不一定是答案，所以比较b，c重复上述算法。直到排除n-1个人，则最后一个人不一定是答案，此时再按照题目要求判断这个人是不是答案即可。
实现思路见代码。
代码
#include"bits/stdc++.h"
#define ll long long
#define db(x) cout<<fixed<<setprecision(14)<<#x<<':'<<x<<endl
#define pb push_back
#define mk make_pair
#define pir pair<ll,ll>
#define max(a,b) (a<b?b:a)
#define mix(a,b) (a<b?a:b)
#define vec vector<ll>
using namespace std;
const int N=5e4+10;
ll t;
//arr[i][j]编号为i的运动员在第j场比赛的排名
ll arr[N][5];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--) {
ll n;
cin>>n;
for(ll i=0; i<n; ++i) for(ll j=0; j<5; ++j) cin>>arr[i][j];
ll p=0;//不一定是最强的人的人的编号（待定最强的人的编号）
for(ll i=1; i<n; ++i) {
ll cnt=0;//运动员p排名比运动员i小的比赛场数
for(ll j=0; j<5; ++j) cnt+=arr[p][j]<=arr[i][j];
p=cnt>=3?p:i;//更新待定最强的人的编号
}
for(ll i=0; i<n; ++i) {
if(p==i) continue;//除自己外
ll cnt=0;
for(ll j=0; j<5; ++j) cnt+=arr[p][j]<=arr[i][j];
if(cnt<3) goto fail;
}
goto win;
fail:
p=-2;
win:
cout<<p+1<<endl;
}
return 0;
}
查看7道真题和解析