首页 > 试题广场 >

锦标赛

[编程题]锦标赛
  • 热度指数：626 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 63M，其他语言126M
  • 算法知识视频讲解
组委会正在为美团点评CodeM大赛的决赛设计新赛制。

比赛有 n 个人参加（其中 n 为2的幂），每个参赛者根据资格赛和预赛、复赛的成绩，会有不同的积分。比赛采取锦标赛赛制，分轮次进行，设某一轮有 m 个人参加，那么参赛者会被分为 m/2 组，每组恰好 2 人，m/2 组的人分别厮杀。我们假定积分高的人肯定获胜，若积分一样，则随机产生获胜者。获胜者获得参加下一轮的资格，输的人被淘汰。重复这个过程，直至决出冠军。

现在请问，参赛者小美最多可以活到第几轮（初始为第0轮）？

输入描述:
第一行一个整数 n (1≤n≤ 2^20)，表示参加比赛的总人数。

接下来 n 个数字（数字范围：-1000000…1000000），表示每个参赛者的积分。

小美是第一个参赛者。


输出描述:
小美最多参赛的轮次。
示例1

输入

4
4 1 2 3

输出

2
算法知识视频讲解
开通博客
头像 HolgerZhang
发表于 2020-02-16 11:42:32
NC13223 锦标赛 题目 组委会正在为美团点评CodeM大赛的决赛设计新赛制。 比赛有 n 个人参加（其中 n 为2的幂），每个参赛者根据资格赛和预赛、复赛的成绩，会有不同的积分。比赛采取锦标赛赛制，分轮次进行，设某一轮有 m 个人参加，那么参赛者会被分为 m/2 组，每组恰好 2 人，m/2 展开全文
去ta的博客 赞 (51) 回复(1) 收起
头像 shyyhs
发表于 2020-08-19 00:30:57
贪心就完事,1号点是小美,问max.那么就是每次都操作都对小美最有利.如何操作呢?首先呢,假如我是小美,我肯定是把这些数分成2组,一组是比我大的数,另外一组是比我小的数.我希望怎么比赛呢,肯定是我每次跟比我小的数进行比赛,然后比我大的人进行比赛,比我小的人进行比赛,这样子是最优的,然后代码就很好写了 展开全文
去ta的博客 赞 (5) 回复(6) 收起
头像 GipsyAvenger
发表于 2022-05-02 23:05:31
NC13223 锦标赛 题解 题目传送门 这题贪心就完事。 首先读入数组。小美要想赢最多，那么就要跟比自己积分低的人比。所以遍历一遍找 a[1]>=a[i] 的，就是算小美能比赢多少人。 之后，小美要跟这些人分组比，所以要算这些人能比多少轮，只需要算他们能分成多少组就行了。每个组两人中活过来一 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 jzyyyyyy
发表于 2022-07-29 16:57:43
">#include<algorithm> #include<vector> using namespace std; int function(int n, vector<int>& nums){ int count = 0; int 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Mo1e
发表于 2023-04-01 14:34:47
#include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; int a[n]; cin>>a[0]; int leCount=1; 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 winter12
发表于 2020-04-27 15:54:19
include<stdio.h> int main(){ long long int n; scanf("%lld",&n); long long int hh; scanf("%lld",&hh); long long int min=1; 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 简简单单无需鼓吹
发表于 2022-08-04 19:24:52
思路 统计 积分小于等于小美(含小美)的人数cnt 判断经过多少次cnt=1(cnt=1,表明在小于等于小美积 分的群体中,产生了冠军),也是小美最多能活的轮次. #include<iostream> using namespace std; const int N=3e6+7; int 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 apeKaiser
发表于 2022-03-17 15:29:35
#include<bits/stdc++.h> using namespace std; const int N = (1 << 21); int a[N]; int main(){ int n; scanf("%d", &n); for 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 A_normal_man
发表于 2022-09-14 09:54:57
可以用模拟的思路来处理这个问题。 Tip：当lar为奇数时，显然seq中要出一个数与其配对，配对结果是lar保留，seq被减一。 #include<iostream> #include<algorithm> using namespace std; int main(){ 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客874106683号
发表于 2019-12-16 00:09:47
/先统计出所有参赛者积分中比小美分低的人数count，如果人数count >= n - 1，小美最多能到最后一轮（注意题中给出的初始为第0轮），如果count < n - 1，假定每次比赛小美都和比他积分低的人比，统计小美比赛次数，就是小美最多能到的轮数。/ include using 展开全文
去ta的博客 赞 (0) 回复(2) 收起

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 c#工程师 深度优先搜索(DFS) 美团 测试开发工程师 大数据开发工程师 Java工程师
来自：CodeM 2017美...
难度：
13条回答 6257浏览

热门推荐

通过挑战的用户

相关试题

锦标赛

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号