当前位置: 代码迷 >> 综合 >> 好题分析--2021.10.23--Codeforce---1552B - Running for Gold
  详细解决方案

好题分析--2021.10.23--Codeforce---1552B - Running for Gold

热度:76   发布时间:2023-11-22 03:48:55.0

题意
如果A的项目有3个的排名比B的高,那么可以认为A打败B,求最后的冠军。

解析
如果直接求的话还是挺麻烦,但是我们观察题意,没有被打败的人一定能称为冠军,被打败的人一定不能称为冠军。因此我们假定第一个人是冠军,依次遍历,如果被打败了,就被将打败我们假定冠军的人假定为冠军,直到最后,第一轮遍历完,除了我们假定的冠军以外的选手都被打败过,我们只要再遍历一次,证明这个冠军是否是真的即可。
 

#include<bits/stdc++.h>
using  namespace  std;
const int N=1e5+5;
int r[N][6];
bool judge(int a,int b){//a打败bint res=0;for(int i=1;i<=5;i++)res+=(r[a][i]<r[b][i]);return res>=3;
}
void solve(){int n;cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=5;j++)scanf("%d",&r[i][j]);int res=1;for(int i=2;i<=n;i++)if(judge(i,res))res=i;for(int i=1;i<=n;i++){if(i!=res && judge(i,res)){printf("-1\n");return ;}}printf("%d\n",res);
}
int main(){int t ;cin>>t;while(t--){solve();}
}

 分析一下本题的思路,也就是先用k筛选出留到最后的人---试图--找到一个可以击败所有人的人,

我们来思考,若一定存在这个人,那么这个人通过筛选一定可以被找出来若不存在这个人,也会筛选出某一个人,那么就需要进行二次判断,看这个人是否真的能击败其他人。

  相关解决方案