1 题目描述

找大佬

众所周知，每个专业里都会有一些大佬隐藏在人群里。软件工程专业也是如此。今天的你就像从人群中找到真正的大腿，找到这个大佬。

假设现在有​名同学（编号为​到​）在班级里，这里面可能存在最多一名大佬。大佬的定义如下：

• 他比其他​个人都强

• 其他​个人都不比他强

我们假设强的关系不一定是绝对的（可能出现我比你强，你也比我强的情况），也不具有传递性（a比b强，b比c强，a不一定比c强），现在给你提供了int better(int a, int b)函数，该函数的参数含义如下：

返回值说明如下：

我们规定自己不比自己强。

你要尽可能少的调用better函数来解决此问题，来找出真正的大佬。

输入描述

输入代码由系统帮助实现，我们约定人数​。

输入第一行包括一个整数​，表示人数。

接下来​行，每行包括​个整数good[i][j]，如果其为​，表示​不比​强，如果其为​表示​比​强。

输出描述

你需要在你的函数里输出你找到的大佬，如果你没有找到，输出-1。

接下来将由系统输出你的询问记录。

当你的答案正确且你询问的次数在标程的3倍以内时，你将AC此题。

预设代码

前置代码

#include
using namespace std;
const int maxn = 1005;
int n;
bool good[maxn][maxn];
void guessdalao(int n); // you should finish this
int better(int a, int b)
{
if (a <= 0 || a > n || b <= 0 || b > n) return -1;
return good[a][b];
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
int t;
scanf("%d", &t);
good[i][j] = t;
}
guessdalao(n);
return 0;
}
/*
void guessdalao(int n)
{
// finish this
}
*/

/* PRESET CODE END - NEVER TOUCH CODE ABOVE */

2 代码

#include   
using namespace std;  
const int maxn = 1005;  
int n;  
bool good[maxn][maxn];  
void guessdalao(int n); // you should finish this  
int better(int a, int b)  
{  if (a <= 0 || a > n || b <= 0 || b > n) return -1;  return good[a][b];  
}  
int main()  
{   freopen("file in.txt","r",stdin);scanf("%d", &n);  for (int i = 1; i <= n; i++)  for (int j = 1; j <= n; j++)  {  int t;  scanf("%d", &t);  good[i][j] = t;  }  guessdalao(n);  return 0;  
}/* 
二分法，每次取两个出来比较，把强者下标存入新的数组，不断重复，直到只剩下一个人，注意奇数时 log2n
把这个强者再和每个人比较一下，确认比每个人强，没人比他强
*/ 
void guessdalao(int n){int stronger[n];int newdata[n];  //用来存储筛选出来的新的强者的下标，待会用来新一轮的筛选int i;int k; //遍历strongerint n0=n; //防止改动nint cmpans,cmpans1;int flag=1;// 不是大佬的标志for(i=0;inewdata[i] = i+1;}//那个强者表里面下标是从1开始的while(1){/*// 错误的把筛选出来的数据和原来的数据进行比较，导致了错乱，应该建立数组把每一次新数据存进去for(i=0,k=0;icmpans = better(newdata[i],newdata[i+1]);if(cmpans==-1){return;}if(cmpans==1){stronger[k]=newdata[i];//把强者的下标存进去k++;}if(cmpans==0){stronger[k]=newdata[i+1];//把强者的下标存进去k++;}}//奇数的情况if(n0%2==1){//这时候i刚好等于n-1；stronger[k]=newdata[i];k++;}n0 = k;if(n0==1){break;//只剩下一个人的时候退出循环}for(i=0;inewdata[i] = stronger[i];}}for(i=0;iif(stronger[0]==i+1){continue;/// 遇到自己不比较}cmpans = better(stronger[0],i+1);cmpans1 = better(i+1,stronger[0]);if(cmpans!=1||cmpans1!=0){flag=0;break;}}if(flag==0){//找出来的不是大佬，就是说没有大佬cout<<"-1"<cout<