6. 找大佬
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 | 询问的第二个人 |
返回值说明如下:
返回值 | 说明 |
---|---|
1 | a比b强 |
0 | a不比b强 |
-1 | 参数不合法,遇到这个时,请即时停止你的程序,你将获得Wrong Answer |
我们规定自己不比自己强。
输入描述
输入代码由系统帮助实现,我们约定人数。
,表示人数。
接下来行,每行包括个整数good[i][j]
,如果其为,表示不比强,如果其为表示比强。
输出描述
-1
。
当你的答案正确且你询问的次数在标程的3倍
预设代码
前置代码
/* 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 | 以文本方式显示
| 以文本方式显示
| 1秒 | 153600KB | 0 |
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 n0=n; //防止改动nint cmpans,cmpans1;int flag=1;// 不是大佬的标志for(i=0;i<n;i++){newdata[i] = i+1;}//那个强者表里面下标是从1开始的while(1){/*// 错误的把筛选出来的数据和原来的数据进行比较,导致了错乱,应该建立数组把每一次新数据存进去for(i=0,k=0;i<n0-1;i+=2){cmpans = better(i+1,i+2);if(cmpans==-1){return;}if(cmpans==1){stronger[k]=i+1;//把强者的下标存进去k++;}if(cmpans==0){stronger[k]=i+2;//把强者的下标存进去k++;}}*/for(i=0,k=0;i<n0-1;i+=2){cmpans = 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;i<n0;i++){newdata[i] = stronger[i];}}for(i=0;i<n;i++){if(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"<<endl;}if(flag==1){cout<<stronger[0]<<endl;}} // void guessdalao(int n)
// {
// int mate[n],i,j,k,l,m,choose[n];
// int temp,addtemp;
// int n0=n,n1=n,flag=1;
// for(i=0;i<n;i++) mate[i]=i+1; //record the mate // while(1)
// {
// for(j=1,k=0;j<n1;j+=2,k++)
// {
// temp=better(mate[j-1],mate[j]);
// if(temp==1) choose[k]=mate[j-1]; //choose the stronger
// if(temp==0) choose[k]=mate[j];
// //printf("%d,%d,%d\n",k,j,choose[k]) ;
// } // if(n1%2==1)
// {
// choose[k]=mate[n1-1];
// k=k+1;
// } //remain the odd number
// n1=k;
// for(l=0;l<n1;l++) mate[l]=choose[l]; //remain stronger ones
// if(n1==1) break;
// }
// //("%d\n",mate[0]);
// for(m=1;(m<n0+1)&&(flag==1);m++) //compare the one who wins with all the orignal mate
// {
// if(mate[0]==m) continue;
// temp=better(mate[0],m);
// addtemp=better(m,mate[0]);
// if((temp!=1)||(addtemp!=0))
// {
// flag=0;
// //printf("02\n");
// break;
// }
// }
// if(flag==0) printf("-1\n");
// if(flag==1) printf("%d\n",mate[0]);
// }
相关文章:
6. 找大佬
1 题目描述 找大佬成绩20开启时间2021年09月24日 星期五 18:00折扣0.8折扣时间2021年11月15日 星期一 00:00允许迟交否关闭时间2021年11月23日 星期二 10:00 众所周知,每个专业里都会有一些大佬隐藏在人群里。软件工程专业也是如此。今天的你就像从人群中找到真正的…...

【CSS】标签显示模式 ① ( 标签显示模式 | 块级元素 )
文章目录一、标签显示模式 ( 块级元素 | 行内元素 )二、块级元素1、块级元素简介2、块级元素特点3、文字块级元素4、代码示例一、标签显示模式 ( 块级元素 | 行内元素 ) 标签显示模式 : 指的是 标签显示的方式 , 标签类型有很多 , 不同的情景使用不同类型的标签 ; 块级元素 : …...

hive真实表空间大小统计
1. 问题 如果是采用hdfs上传加载的表、或者是flume直接写hdfs的表空间通常看hive的属性是不准确的。 2. 思路 为了使结果更精确,我们直接使用linux下命令统计hive仓库目录下的每个表对应的文件夹目录占用空间的大小。 3. 解决方法 这里建立三层表结构 ods: 原始…...
微信小程序引入Vant UI步骤
官方文档教程 1、通过 npm 安装 # 通过 npm 安装 npm i vant/weapp -S --production# 通过 yarn 安装 yarn add vant/weapp --production# 安装 0.x 版本 npm i vant-weapp -S --production2、修改 app.json 将 app.json 中的 “style”: “v2” 去除,小程序的新…...
【震撼发布】《致敬未来的攻城狮计划》| 文末赠书3本
《致敬未来的攻城狮计划》—— 文末有福利 摘要: 一个崭新的计划,寻找那群有志于向嵌入式发展的未来工程师! 文章目录1 活动计划初衷2 活动计划形式3 活动计划收获4 活动计划要求5 活动计划时间6 活动计划致谢7 活动计划特别说明8 温馨提示9 …...

8.装饰者模式
目录 简介 角色组成 实现步骤 1. 新建 Log.class,添加如下代码 2. 新建 Log4j.class,继承 Log.class,并实现 record() 方法 3. 新建 Decorator.class,继承 Log.class 4. 新建 Log4jDecorator.class,继承 Decorat…...

GIT基础常用命令-1 GIT基础篇
git基础常用命令-1 GIT基础篇1.git简介及配置1.1 git简介1.2 git配置config1.2.1 查看配置git config1.2.2 配置设置1.2.3 获取帮助git help2 GIT基础常用命令2.1 获取镜像仓库2.1.1 git init2.1.2 git clone2.2 本地仓库常用命令2.2.1 git status2.2.2 git add2.2.3 git diff2…...

华为OD机试题,用 Java 解【数列描述】问题
华为Od必看系列 华为OD机试 全流程解析+经验分享,题型分享,防作弊指南)华为od机试,独家整理 已参加机试人员的实战技巧华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典使用说明 参加华为od机试,一定要注意不…...

2022掉队的“蔚小理”,按下了兔年加速键
配图来自Canva可画 进入2023年,各大车企又展开了新一轮的“竞速”。尽管1月份汽车整体销量出现了“阴跌”,但从各路车企发布的销量目标来看,车企对于2023依旧保持着较高的信心和预期。在一众车企中,以“蔚小理”为代表的新势力们…...

【NLP相关】attention的代码实现
❤️觉得内容不错的话,欢迎点赞收藏加关注😊😊😊,后续会继续输入更多优质内容❤️👉有问题欢迎大家加关注私戳或者评论(包括但不限于NLP算法相关,linux学习相关,读研读博…...

凌恩生物资讯
凌恩生物转录组项目包含范围广,项目经验丰富,人均10年以上项目经验,其中全长转录组测序研究基因结构已经成为发文章的趋势,研究物种包括高粱、玉米、拟南芥、鸡、人和小鼠、毛竹、棉花等。凌恩生物提供专业的全长转录组测序及分析…...
Leetcode 148. 排序链表(二路归并)
题目: 给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。 解法一: 递归解法,自顶向下 链表版二路归并排序(升序,递归版),稳定排序 时间复杂度…...

记录Paint部分常用的方法
Paint部分常用的方法1、实例化之后Paint的基本配置2、shader 和 ShadowLayer3、pathEffect4、maskFilter5、colorFilter6、xfermode1、实例化之后Paint的基本配置 Paint.Align Align指定drawText如何将其文本相对于[x,y]坐标进行对齐。默认为LEFTPaint.Cap Cap指定了笔画线和路…...

ArrayList集合底层原理
ArrayList集合底层原理ArrayList集合底层原理1.介绍2.底层实现3.构造方法3.1集合的属性4.扩容机制5.其他方法6.总结ArrayList集合底层原理 1.介绍 ArrayList是List接口的可变数组的实现。实现了所有可选列表操作,并允许包括 null 在 内的所有元素。 每个 Array…...

内网部署swagger快解析映射方案发布让外网访问
计算机业内人士对于swagger并不陌生, 不少人选择用swagger做为API接口文档管理。Swagger 是一个规范和完整的框架,用于生成、描述、调用和可视化 RESTful 风格的 Web 服务。总体目标是使客户端和文件系统作为服务器以同样的速度来更新文件的方法&#x…...

全网最全整理,自动化测试10种场景处理(超详细)解决方案都在这......
目录:导读前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结(尾部小惊喜)前言 自动化工作流程 自动…...
【c++】指针的学习
指针是C中非常重要的概念,理解指针的使用可以使程序更高效,并且可以处理更加复杂的数据结构。 指针是一个变量,它存储了另一个变量的地址。通过指针访问这个变量可以提高程序的效率,尤其是在处理大型数据结构时。 在C中࿰…...

华为OD机试题,用 Java 解【水仙花数】问题
华为Od必看系列 华为OD机试 全流程解析+经验分享,题型分享,防作弊指南)华为od机试,独家整理 已参加机试人员的实战技巧华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典使用说明 参加华为od机试,一定要注意不…...

【Linux】-- 基本指令
目录 用户管理 adduser passwd userdel pwd ls指令 -l -a -d -F -r -t -R -1 which alias ll ls -n cd cd - cd ~ touch -d stat mkdir -p rmdir rm -r -f man cp 编辑 -r -f mv cat -n tac more less -N head tail | 管道 dat…...

JavaScript 中的 String 类型 模板字面量定义字符串
ECMAScript 6新增了使用模板字面量定义字符串的能力。与使用单引号或双引号不同,模板字面量保留换行字符,可以跨行定义字符串: let str1 早起的年轻人\n喜欢经常跳步;let str2 早起的年轻人喜欢经常跳步;console.log(str1);// 早起的年轻人…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)
macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 🍺 最新版brew安装慢到怀疑人生?别怕,教你轻松起飞! 最近Homebrew更新至最新版,每次执行 brew 命令时都会自动从官方地址 https://formulae.…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...
k8s从入门到放弃之HPA控制器
k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率(或其他自定义指标)来调整这些对象的规模,从而帮助应用程序在负…...

软件工程 期末复习
瀑布模型:计划 螺旋模型:风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合:模块内部功能紧密 模块之间依赖程度小 高内聚:指的是一个模块内部的功能应该紧密相关。换句话说,一个模块应当只实现单一的功能…...

uni-app学习笔记三十五--扩展组件的安装和使用
由于内置组件不能满足日常开发需要,uniapp官方也提供了众多的扩展组件供我们使用。由于不是内置组件,需要安装才能使用。 一、安装扩展插件 安装方法: 1.访问uniapp官方文档组件部分:组件使用的入门教程 | uni-app官网 点击左侧…...