一、鏈接
比賽
二、題目
題目描述
有n個(gè)人要進(jìn)行比賽，比賽規(guī)則如下：
- 假設(shè)每輪比賽的人是m，取最大的k，k=2^t且k≤m。這k個(gè)人每2人舉行一場(chǎng)比賽，勝利者進(jìn)入一下輪，失敗者被淘汰。
- 余下的m-k個(gè)人，不進(jìn)行比賽，直接進(jìn)入下一輪
- 直到?jīng)Q出冠軍，比賽結(jié)束。
比如有5個(gè)人參加比賽，第一輪舉辦2場(chǎng)，剩余3人進(jìn)入第二輪，第二輪1場(chǎng)，剩余2人進(jìn)入第三輪，第三輪舉辦1場(chǎng)決出冠軍，所以一共要辦4場(chǎng)比賽。 請(qǐng)問一共要舉行幾輪多少場(chǎng)比賽？
輸入
第一行是一個(gè)整數(shù)K，表示樣例的個(gè)數(shù)。 以后每行一個(gè)樣例，為n(1≤n≤1000000000)
輸出
每行輸出兩個(gè)整數(shù)，輪數(shù)和比賽場(chǎng)數(shù)，中間用一個(gè)空格隔開。
樣例輸入
2 1 5
樣例輸出
0 0 3 4
三、題意
有n個(gè)人進(jìn)行比賽，最后只剩下一個(gè)人，輸出比賽輪數(shù)和比賽場(chǎng)數(shù)，需要找到最大的小于總?cè)藬?shù)n的2的指數(shù)函數(shù)的值k
四、代碼
c++
#include<iostream>
using namespace std;
int main()
{
int t;//表示樣例數(shù)
scanf("%d",&t);
while(t--)
{
int n,k=1,a=0,b=0;//n表示總?cè)藬?shù)，k表示最接近n的2的指數(shù)函數(shù)的值
//a表示輪數(shù)，b表示場(chǎng)數(shù)
scanf("%d",&n);
if(n<2) printf("0 0\n");//只剩下一個(gè)人，就不需要比較，特判
else
{
while(n>1)//只要不是剩下一個(gè)人，就一直循環(huán)
{
while(k<n) k*=2;//尋找最接近n的2的指數(shù)函數(shù)的值
if(k!=n) k/=2;//跳出上面循環(huán)會(huì)多乘一次，所以除掉一個(gè)2
//當(dāng)然，k==n不算多乘了一次，條件判斷if(k>n)也是可以的
a++;//每一次算一輪
b+=k/2;//比賽進(jìn)行k/2場(chǎng)
n-=k/2;//淘汰k/2個(gè)人
}
printf("%d %d\n",a,b);
}
}
return 0;
}c語(yǔ)言
#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;
}五、總結(jié)
1.怎么找到最大的小于總?cè)藬?shù)n的2的指數(shù)函數(shù)數(shù)值k:使用一個(gè)循環(huán)，讓k從1開始循環(huán)，每一次循環(huán)把k乘以2，一直到k大于n的時(shí)候跳出循環(huán)
while(k<n) k*=2;這個(gè)時(shí)候需要注意一個(gè)特判：如果兩個(gè)數(shù)字相等怎么辦（如果總?cè)藬?shù)n是偶數(shù)）？好吧，其實(shí)是因?yàn)槲覍忣}的時(shí)候沒有仔細(xì)，題目說了是k<=m，意思也就是說等于也是可以的，當(dāng)然我們模擬發(fā)現(xiàn)也是可以的......(多此一舉了)?
#include<iostream>
using namespace std;
int main()
{
int t;//表示樣例數(shù)
scanf("%d",&t);
while(t--)
{
int n,k=1,a=0,b=0;//n表示總?cè)藬?shù)，k表示最接近n的2的指數(shù)函數(shù)的值
//a表示輪數(shù)，b表示場(chǎng)數(shù)
scanf("%d",&n);
if(n<2) printf("0 0\n");//只剩下一個(gè)人，就不需要比較，特判
else
{
while(n>1)//只要不是剩下一個(gè)人，就一直循環(huán)
{
while(k<=n) k*=2;//尋找最接近n的2的指數(shù)函數(shù)的值
k/=2;//跳出上面循環(huán)會(huì)多乘一次，所以除掉一個(gè)2
//當(dāng)然，k==n不算多乘了一次，條件判斷if(k>n)也是可以的
a++;//每一次算一輪
b+=k/2;//比賽進(jìn)行k/2場(chǎng)
n-=k/2;//淘汰k/2個(gè)人
}
printf("%d %d\n",a,b);
}
}
return 0;
}改成這樣甚至不用再多加一個(gè)條件判斷，可以肯定多乘了一次2，所以直接除以一次2即可，這個(gè)就是跳出循環(huán)的臨界條件，只有k>n才會(huì)跳出循環(huán)，但是這個(gè)時(shí)候k是不滿足條件的，所以需要回退一次，也就是除以2
?2.輪數(shù)，場(chǎng)數(shù)，總?cè)藬?shù)之間的關(guān)系是什么？
每一輪需要算出一個(gè)小于等于總?cè)藬?shù)n的一個(gè)最大的2的指數(shù)函數(shù)數(shù)值k
每一輪需要進(jìn)行k/2場(chǎng)比賽
每一輪需要淘汰k/2個(gè)人
不斷地更新輪數(shù)，場(chǎng)數(shù)，總?cè)藬?shù)，不大于總?cè)藬?shù)的最大的2的指數(shù)函數(shù)數(shù)值k即可
3.比賽最后只要留下一個(gè)冠軍，也就是說總?cè)藬?shù)等于1是結(jié)束的標(biāo)識(shí)，跳出循環(huán)的臨界條件
六、精美圖片
文章來源：http://www.zghlxwxcb.cn/news/detail-640269.html
?文章來源地址http://www.zghlxwxcb.cn/news/detail-640269.html
到了這里，關(guān)于湘大 XTU OJ 1308 比賽 題解：循環(huán)結(jié)束的臨界點(diǎn)+樸素模擬的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
