湘大 XTU OJ 1308 比赛 题解:循环结束的临界点+朴素模拟

一、链接

比赛

二、题目

题目描述

n个人要进行比赛,比赛规则如下:

  1. 假设每轮比赛的人是m,取最大的kk=2^t且k≤m。这k个人每2人举行一场比赛,胜利者进入一下轮,失败者被淘汰。
  2. 余下的m-k个人,不进行比赛,直接进入下一轮
  3. 直到决出冠军,比赛结束

比如有5个人参加比赛,第一轮举办2场,剩余3人进入第二轮,第二轮1场,剩余2人进入第三轮,第三轮举办1场决出冠军,所以一共要办4场比赛。 请问一共要举行几轮多少场比赛?

输入

第一行是一个整数K,表示样例的个数。 以后每行一个样例,为n(1≤n≤1000000000)

输出

每行输出两个整数,轮数和比赛场数,中间用一个空格隔开。

样例输入

2
1
5

样例输出

0 0
3 4

三、题意

有n个人进行比赛,最后只剩下一个人,输出比赛轮数和比赛场数,需要找到最大的小于总人数n的2的指数函数的值k

四、代码

c++

#include<iostream>using namespace std;int main()
{int t;//表示样例数scanf("%d",&t);while(t--){int n,k=1,a=0,b=0;//n表示总人数,k表示最接近n的2的指数函数的值//a表示轮数,b表示场数scanf("%d",&n);if(n<2)	printf("0 0\n");//只剩下一个人,就不需要比较,特判else{while(n>1)//只要不是剩下一个人,就一直循环{while(k<n)	k*=2;//寻找最接近n的2的指数函数的值if(k!=n)	k/=2;//跳出上面循环会多乘一次,所以除掉一个2//当然,k==n不算多乘了一次,条件判断if(k>n)也是可以的a++;//每一次算一轮b+=k/2;//比赛进行k/2场n-=k/2;//淘汰k/2个人}printf("%d %d\n",a,b);}}return 0;
}

c语言

#include<stdio.h>int main()
{int t;scanf("%d",&t);while(t--){int n,k=1,a=0,b=0;scanf("%d",&n);if(n<2)	printf("0 0\n");else{while(n>1){while(k<n)	k*=2;if(k>n)	k/=2;a++;b+=k/2;n-=k/2;}printf("%d %d\n",a,b);}}return 0;
}

五、总结

1.怎么找到最大的小于总人数n的2的指数函数数值k:使用一个循环,让k从1开始循环,每一次循环把k乘以2,一直到k大于n的时候跳出循环

while(k<n)	k*=2;

这个时候需要注意一个特判:如果两个数字相等怎么办(如果总人数n是偶数)?好吧,其实是因为我审题的时候没有仔细,题目说了是k<=m,意思也就是说等于也是可以的,当然我们模拟发现也是可以的......(多此一举了) 

#include<iostream>using namespace std;int main()
{int t;//表示样例数scanf("%d",&t);while(t--){int n,k=1,a=0,b=0;//n表示总人数,k表示最接近n的2的指数函数的值//a表示轮数,b表示场数scanf("%d",&n);if(n<2)	printf("0 0\n");//只剩下一个人,就不需要比较,特判else{while(n>1)//只要不是剩下一个人,就一直循环{while(k<=n)	k*=2;//寻找最接近n的2的指数函数的值k/=2;//跳出上面循环会多乘一次,所以除掉一个2//当然,k==n不算多乘了一次,条件判断if(k>n)也是可以的a++;//每一次算一轮b+=k/2;//比赛进行k/2场n-=k/2;//淘汰k/2个人}printf("%d %d\n",a,b);}}return 0;
}

改成这样甚至不用再多加一个条件判断,可以肯定多乘了一次2,所以直接除以一次2即可,这个就是跳出循环的临界条件,只有k>n才会跳出循环,但是这个时候k是不满足条件的,所以需要回退一次,也就是除以2

 2.轮数,场数,总人数之间的关系是什么?

每一轮需要算出一个小于等于总人数n的一个最大的2的指数函数数值k

每一轮需要进行k/2场比赛

每一轮需要淘汰k/2个人

不断地更新轮数,场数,总人数,不大于总人数的最大的2的指数函数数值k即可

3.比赛最后只要留下一个冠军,也就是说总人数等于1是结束的标识,跳出循环的临界条件

六、精美图片

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/85812.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

iOS问题记录 - Xcode 15安装低版本iOS模拟器(持续更新)

文章目录 前言开发环境问题描述问题分析1. 定位问题2. 逆向分析2.1. IDA Free2.2. Hopper Disassembler Demo 3. 模拟器日志4. supportedArchs 解决方案最后 前言 最近新需求很多&#xff0c;项目改动很大&#xff0c;开发完成后想测一遍在低版本iOS系统上的兼容性&#xff0c…

Oracle 开发篇+Java通过共享模式访问Oracle数据库

标签&#xff1a;共享服务器进程、shared server process释义&#xff1a;shared server process是Oracle的一种数据库连接技术&#xff0c;类似的还有专用模式和DRCP ★ 数据库配置 alter system set shared_server_sessions1 scopespfile; alter system set max_shared_serv…

大连交通大学813软件工程考研习题

1.什么是软件生存周期模型?有哪些主要模型? 生存周期模型&#xff1a;描述软件开发过程中各种活动如何执行的模型。对软件开发提供强有力的支持&#xff0c;为开发过程中的活动提供统一的政策保证&#xff0c;为参与开发的人员提供帮助和指导&#xff0c;是软件生存周期模型…

【学习FreeRTOS】第5章——FreeRTOS任务挂起与恢复

1.任务的挂起与恢复的API函数 vTaskSuspend() ——挂起任务&#xff08;类似暂停&#xff0c;可恢复&#xff0c;但删除任务&#xff0c;无法恢复&#xff09;vTaskResume() ——恢复被挂起的任务xTaskResumeFromISR()—— 在中断中恢复被挂起的任务 1.1.任务挂起函数vTaskSu…

Grafana+Prometheus技术文档-进阶使用-监控spring-boot项目

阿丹&#xff1a; 之前已经实现了使用Prometheus来对服务器进行了监控和仪表盘的创建&#xff0c;现在就需要对这些监控方法使用在spring-boot中去。 实现思路&#xff1a; 1、集成Actuator 2、加入Prometheus的依赖 3、配置开放端口、以及开放监控 4、配置Prometheus中的配置…

天马上位在即,将成为iPhoneSE4二级供应商,SE4有望2025年量产

根据知情人士透露&#xff0c;国内OLED面板制造商&#xff0c;如天马&#xff0c;正在积极争取成为苹果iPhone SE 4的AMOLED面板供应商。 苹果面板采购负责人已经在今年上半年访问了中国大陆的主要柔性AMOLED面板制造商之一&#xff0c;这意味着国内一家OLED面板厂商有望成为iP…

【PCL】激光雷达常用传统感知算法学习

&#x1f60f;★,:.☆(&#xffe3;▽&#xffe3;)/$:.★ &#x1f60f; 这篇文章主要介绍常用激光感知算法学习。 无专精则不能成&#xff0c;无涉猎则不能通。——梁启超 欢迎来到我的博客&#xff0c;一起学习&#xff0c;共同进步。 喜欢的朋友可以关注一下&#xff0c;下…

【已解决】Java 中使用 ES 高级客户端库 RestHighLevelClient 清理百万级规模历史数据

&#x1f389;工作中遇到这样一个需求场景&#xff1a;由于ES数据库中历史数据过多&#xff0c;占用太多的磁盘空间&#xff0c;需要定期地进行清理&#xff0c;在一定程度上可以释放磁盘空间&#xff0c;减轻磁盘空间压力。 &#x1f388;在经过调研之后发现&#xff0c;某服务…

9.2.2Socket(TCP)

一.过程: 1.建立连接(不是握手),虽然内核中的连接有很多,但是在应用程序中,要一个一个处理. 2. 获取任务:使用ServerSocket.accept()方法,作用是把内核中的连接获取到应用程序中,这个过程类似于生产者消费者模型. 3. 使用缓冲的时候,注意全缓冲和行缓冲. 4.注意关闭文件资源…

从零实战SLAM-第二课(SLAM中的基础数学)

空间数据的表达方式&#xff1a;点和向量两种形式。 向量的内积&#xff0c;也叫做点乘&#xff0c;是逐点相乘后累加&#xff0c;最终结果是一个标量&#xff0c;物理意义是一个向量在另一个向量上的投影。 外积&#xff0c;也叫做叉乘&#xff0c;两个向量拼起来成&#xff0…

maven是什么?安装+配置

目录 1.什么是maven&#xff1f; 1.2.maven的核心功能是什么&#xff1f; 2.Maven安装配置 2.1Maven的安装 2.2Maven环境配置 1.配置 MAVEN_HOME &#xff0c;变量值就是你的 maven 安装的路径&#xff08;bin 目录之前一级目录&#xff09; 2.将MAVEN_HOME 添加到Path系…

汽车上的电源模式详解

① 一般根据钥匙孔开关的位置来确定整车用电类别&#xff0c;汽车上电源可以分为常电&#xff0c;IG电&#xff0c;ACC电 1&#xff09;常电。常电表示蓄电池和发电机输出直接供电&#xff0c;即使点火开关在OFF档时&#xff0c;也有电量供应。一般来讲模块的记忆电源及需要在车…

关于安卓打包生成aar,jar实现(一)

关于安卓打包生成aar&#xff0c;jar方式 背景 在开发的过程中&#xff0c;主项目引入三方功能的方式有很多&#xff0c;主要是以下几个方面&#xff1a; &#xff08;1&#xff09;直接引入源代码module&#xff08;优点&#xff1a;方便修改源码&#xff0c;易于维护&#…

ArcGIS Pro技术应用(暨基础入门、制图、空间分析、影像分析、三维建模、空间统计分析与建模、python融合)

GIS是利用电子计算机及其外部设备&#xff0c;采集、存储、分析和描述整个或部分地球表面与空间信息系统。简单地讲&#xff0c;它是在一定的地域内&#xff0c;将地理空间信息和 一些与该地域地理信息相关的属性信息结合起来&#xff0c;达到对地理和属性信息的综合管理。GIS的…

golang trace view 视图详解

大家好&#xff0c;我是蓝胖子&#xff0c;在golang中可以使用go pprof的工具对golang程序进行性能分析&#xff0c;其中通过go trace 命令生成的trace view视图对于我们分析系统延迟十分有帮助&#xff0c;鉴于当前对trace view视图的介绍还是很少&#xff0c;在粗略的看过tra…

MySQL存储结构及索引

文章目录 MySQL结构1.2存储引擎介绍1.3存储引擎特点InnoDB逻辑存储结构 MyISAMMemory区别及特点存储引擎选择 索引索引概述索引结构BTreeHash索引分类聚集索引&二级索引索引语法SQL性能分析索引优化最左前缀法则范围查询字符串不加引号模糊查询or连接条件数据分布影响覆盖索…

Linux:Shell编程之正则表达式

目录 绪论 1、正则表达式 1.1 通配符 1.2 正则表达式分类 1.3 基本正则 1.4 正则表达式中表示次数的表达式 1.5 位置锚定 1.5.1 词首锚定和词尾锚定 1.6 分组&#xff08;&#xff09; 1.7 逻辑或 1.8 扩展正则 绪论 正则表达式&#xff1a;有一类特殊字符以及文本…

.NET对象的内存布局

在.NET中&#xff0c;理解对象的内存布局是非常重要的&#xff0c;这将帮助我们更好地理解.NET的运行机制和优化代码&#xff0c;本文将介绍.NET中的对象内存布局。 .NET中的数据类型主要分为两类&#xff0c;值类型和引用类型。值类型包括了基本类型(如int、bool、double、cha…

SQL server 与 MySQL count函数、以及sum、avg 是否包含 为null的值

sql server 与 mysql count 作用一样。 count 计算指定字段出现的个数&#xff0c; 不是计算 null的值 获取表的条数 count(n) n:常数 count(1),count&#xff08;0&#xff09;等 count(*) count(字段) 其中字段为null 不会统计在内。 avg(字段)、sum(字段) 跟count(字段)…

VS Code 使用cnpm下载包失败

一、 问题如下&#xff1a; 网上找到的解决方法是要在powershell中执行&#xff1a; Set-ExecutionPolicy RemoteSigned进行更改策略。 首先我们解释下这个Set-ExecutionPolicy RemoteSigned&#xff0c;Set-ExecutionPolicy 是一个 PowerShell 命令&#xff0c;用于控制脚本…