企业网站 建设流程,免费学做淘宝的网站,门户网站系统设计,斗鱼类的直播网站开发1 题目描述
找大佬成绩20开启时间2021年09月24日 星期五 18:00折扣0.8折扣时间2021年11月15日 星期一 00:00允许迟交否关闭时间2021年11月23日 星期二 10:00 众所周知#xff0c;每个专业里都会有一些大佬隐藏在人群里。软件工程专业也是如此。今天的你就像从人群中找到真正的…1 题目描述
找大佬
成绩20开启时间2021年09月24日 星期五 18:00折扣0.8折扣时间2021年11月15日 星期一 00:00允许迟交否关闭时间2021年11月23日 星期二 10:00 众所周知每个专业里都会有一些大佬隐藏在人群里。软件工程专业也是如此。今天的你就像从人群中找到真正的大腿找到这个大佬。 假设现在有名同学编号为到在班级里这里面可能存在最多一名大佬。大佬的定义如下 他比其他个人都强 其他个人都不比他强 我们假设强的关系不一定是绝对的可能出现我比你强你也比我强的情况也不具有传递性a比b强b比c强a不一定比c强现在给你提供了int better(int a, int b)函数该函数的参数含义如下 参数说明a询问的第一个人b询问的第二个人 返回值说明如下 返回值说明1a比b强0a不比b强-1参数不合法遇到这个时请即时停止你的程序你将获得Wrong Answer 我们规定自己不比自己强。 你要尽可能少的调用better函数来解决此问题来找出真正的大佬。 输入描述 输入代码由系统帮助实现我们约定人数。 输入第一行包括一个整数表示人数。 接下来行每行包括个整数good[i][j]如果其为表示不比强如果其为表示比强。 输出描述 你需要在你的函数里输出你找到的大佬如果你没有找到输出-1。 接下来将由系统输出你的询问记录。 当你的答案正确且你询问的次数在标程的3倍以内时你将AC此题。预设代码前置代码/* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */ #include bits/stdc.h 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 */ 测试输入 期待的输出 时间限制 内存限制 额外进程 测试用例 1以文本方式显示2↵0 0↵1 0↵以文本方式显示2↵3↵2 1↵1 2↵2 1↵1秒153600KB0 2 代码
#include bits/stdc.h
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 n0n; //防止改动nint cmpans,cmpans1;int flag1;// 不是大佬的标志for(i0;in;i){newdata[i] i1;}//那个强者表里面下标是从1开始的while(1){/*// 错误的把筛选出来的数据和原来的数据进行比较导致了错乱应该建立数组把每一次新数据存进去for(i0,k0;in0-1;i2){cmpans better(i1,i2);if(cmpans-1){return;}if(cmpans1){stronger[k]i1;//把强者的下标存进去k;}if(cmpans0){stronger[k]i2;//把强者的下标存进去k;}}*/for(i0,k0;in0-1;i2){cmpans better(newdata[i],newdata[i1]);if(cmpans-1){return;}if(cmpans1){stronger[k]newdata[i];//把强者的下标存进去k;}if(cmpans0){stronger[k]newdata[i1];//把强者的下标存进去k;}}//奇数的情况if(n0%21){//这时候i刚好等于n-1stronger[k]newdata[i];k;}n0 k;if(n01){break;//只剩下一个人的时候退出循环}for(i0;in0;i){newdata[i] stronger[i];}}for(i0;in;i){if(stronger[0]i1){continue;/// 遇到自己不比较}cmpans better(stronger[0],i1);cmpans1 better(i1,stronger[0]);if(cmpans!1||cmpans1!0){flag0;break;}}if(flag0){//找出来的不是大佬就是说没有大佬cout-1endl;}if(flag1){coutstronger[0]endl;}} // void guessdalao(int n)
// {
// int mate[n],i,j,k,l,m,choose[n];
// int temp,addtemp;
// int n0n,n1n,flag1;
// for(i0;in;i) mate[i]i1; //record the mate // while(1)
// {
// for(j1,k0;jn1;j2,k)
// {
// tempbetter(mate[j-1],mate[j]);
// if(temp1) choose[k]mate[j-1]; //choose the stronger
// if(temp0) choose[k]mate[j];
// //printf(%d,%d,%d\n,k,j,choose[k]) ;
// } // if(n1%21)
// {
// choose[k]mate[n1-1];
// kk1;
// } //remain the odd number
// n1k;
// for(l0;ln1;l) mate[l]choose[l]; //remain stronger ones
// if(n11) break;
// }
// //(%d\n,mate[0]);
// for(m1;(mn01)(flag1);m) //compare the one who wins with all the orignal mate
// {
// if(mate[0]m) continue;
// tempbetter(mate[0],m);
// addtempbetter(m,mate[0]);
// if((temp!1)||(addtemp!0))
// {
// flag0;
// //printf(02\n);
// break;
// }
// }
// if(flag0) printf(-1\n);
// if(flag1) printf(%d\n,mate[0]);
// }
