題目

如果要在n個(gè)數(shù)據(jù)中挑選出第一大和第二大的數(shù)據(jù)（要求輸出數(shù)據(jù)所在位置和值），使用什么方法比較的次數(shù)最少？
我們可以從體育錦標(biāo)賽中受到啟發(fā)。

如圖【1.png】所示，8個(gè)選手的錦標(biāo)賽，先兩兩捉對(duì)比拼，淘汰一半。優(yōu)勝者再兩兩比拼…直到?jīng)Q出第一名。

第一名輸出后，只要對(duì)黃色標(biāo)示的位置重新比賽即可。

下面的代碼實(shí)現(xiàn)了這個(gè)算法（假設(shè)數(shù)據(jù)中沒有相同值）。

代碼中需要用一個(gè)數(shù)組來表示圖中的樹（注意，這是個(gè)滿二叉樹，不足需要補(bǔ)齊）。
它不是存儲(chǔ)數(shù)據(jù)本身，而是存儲(chǔ)了數(shù)據(jù)的下標(biāo)。

第一個(gè)數(shù)據(jù)輸出后，它所在的位置被標(biāo)識(shí)為-1

//重新決出k號(hào)位置，v為已輸出值 void pk(int* a, int* b, int n, int k, int v) {int k1 = k*2 + 1;int k2 = k1 + 1;if(k1>=n || k2>=n){b[k] = -1;return;}if(b[k1]==v)pk(a,b,n,k1,v);elsepk(a,b,n,k2,v);//重新比較if(b[k1]<0){if(b[k2]>=0)b[k] = b[k2];elseb[k] = -1;return;}if(b[k2]<0){if(b[k1]>=0)b[k] = b[k1];elseb[k] = -1;return;}if(______________________) //填空b[k] = b[k1];elseb[k] = b[k2]; }//對(duì)a中數(shù)據(jù)，輸出最大，次大元素位置和值 void f(int* a, int len) {int n = 1;while(n<len) n *= 2;int* b = (int*)malloc(sizeof(int*) * (2*n-1));int i;for(i=0; i<n; i++){if(i<len)b[n-1+i] = i;elseb[n-1+i] = -1;}//從最后一個(gè)向前處理for(i=2*n-1-1; i>0; i-=2){if(b[i]<0){if(b[i-1]>=0)b[(i-1)/2] = b[i-1];elseb[(i-1)/2] = -1;}else{if(a[b[i]]>a[b[i-1]])b[(i-1)/2] = b[i];elseb[(i-1)/2] = b[i-1];}}//輸出樹根printf("%d : %d\n", b[0], a[b[0]]);//值等于根元素的需要重新pkpk(a,b,2*n-1,0,b[0]);//再次輸出樹根printf("%d : %d\n", b[0], a[b[0]]);free(b); }int main() {int a[] = {54,55,18,16,122,17,30,9,58};dfs(a,9); } 請(qǐng)仔細(xì)分析流程，填寫缺失的代碼。通過瀏覽器提交答案，只填寫缺失的代碼，不要填寫已有代碼或其它說明語(yǔ)句等。

代碼

#include <iostream> using namespace std;//重新決出k號(hào)位置，v為已輸出值 //a原始數(shù)據(jù)，b是樹，n=31，k=0是下標(biāo)，v是第一大的值的下標(biāo) void pk(int* a, int* b, int n, int k, int v) {int k1 = k*2 + 1;//k的左子下標(biāo)int k2 = k1 + 1;//右子下標(biāo)if(k1>=n || k2>=n){//超出樹的邊界，k一定是葉子，b[k]-1b[k] = -1;return;}//沿著冠軍的路，一直追溯到第一次比賽if(b[k1]==v)pk(a,b,n,k1,v);elsepk(a,b,n,k2,v);//到此，k就是冠軍一開始的下標(biāo),此時(shí)b[k]=-1//重新比較if(b[k1]<0){//if(b[k2]>=0)b[k] = b[k2];//左子<0，右子>0,選右子elseb[k] = -1;//都小于0 標(biāo)記為-1return;}if(b[k2]<0){if(b[k1]>=0)b[k] = b[k1];elseb[k] = -1;return;}if(a[b[k1]]>a[b[k2]]) //填空b[k] = b[k1];elseb[k] = b[k2]; }//對(duì)a中數(shù)據(jù)，輸出最大，次大元素位置和值 void f(int* a, int len) {int n = 1;while(n<len) n *= 2; // n=16 2n-1=31 //開辟樹的空間 ll=31 樹數(shù)組的長(zhǎng)度int* b = (int*)malloc(sizeof(int*) * (2*n-1));int i; // 初始化樹的最下層for(i=0; i<n; i++){if(i<len)b[n-1+i] = i;elseb[n-1+i] = -1;}//從最后一個(gè)向前處理 2*n-1-1是b數(shù)組的最大小標(biāo)for(i=2*n-1-1; i>0; i-=2){if(b[i]<0){//i一開始一定指向右孩子，每次-2還是右孩子if(b[i-1]>=0)//兄弟大于0，父節(jié)點(diǎn)的值就是兄弟節(jié)點(diǎn)的值，父節(jié)點(diǎn)b[(i-1)/2]b[(i-1)/2] = b[i-1];else //兩個(gè)孩子都是-1b[(i-1)/2] = -1;}else{//自身不是-1，左兄弟也一定不是-1if(a[b[i]]>a[b[i-1]])//pk，誰(shuí)代表的原始數(shù)據(jù)更大，誰(shuí)上b[(i-1)/2] = b[i];elseb[(i-1)/2] = b[i-1];}} // 第一輪pk結(jié)束//輸出樹根printf("%d : %d\n", b[0], a[b[0]]);//值等于根元素的需要重新pk 2*n-1=31pk(a,b,2*n-1,0,b[0]);//再次輸出樹根printf("%d : %d\n", b[0], a[b[0]]);free(b); }int main() {int a[] = {154,55,18,16,122,17,130,9,58};//原始數(shù)據(jù)f(a,9); }

總結(jié)

以上是生活随笔為你收集整理的征战蓝桥 —— 2014年第五届 —— C/C++A组第5题——锦标赛的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。