LQ0197 锦标赛【程序填空】

题目来源：蓝桥杯2014初赛 C++ A组E题

题目描述
本题为代码补全填空题，请将题目中给出的源代码补全，并复制到右侧代码框中，选择对应的编译语言（C/Java）后进行提交。若题目中给出的源代码语言不唯一，则只需选择其一进行补全提交即可。复制后需将源代码中填空部分的下划线删掉，填上你的答案。提交后若未能通过，除考虑填空部分出错外，还需注意是否因在复制后有改动非填空部分产生错误。

如果要在 n 个数据中挑选出第一大和第二大的数据（要求输出数据所在位置和值），使用什么方法比较的次数最少？我们可以从体育锦标赛中受到启发。

如下图所示，8 个选手的锦标赛，先两两捉对比拼，淘汰一半。优胜者再两两比拼…直到决出第一名。

第一名输出后，只要对黄色标示的位置重新比赛即可。

下面的代码实现了这个算法（假设数据中没有相同值）。

代码中需要用一个数组来表示图中的树（注意，这是个满二叉树，不足需要补齐）。它不是存储数据本身，而是存储了数据的下标。

第一个数据输出后，它所在的位置被标识为 -1。

请分析程序流程，填写划线部分缺少的代码。

源代码
C

#include 
#include 

//重新决出k号位置，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);
    else
        pk(a,b,n,k2,v);
    
    //重新比较
    if(b[k1]<0){
        if(b[k2]>=0)
            b[k] = b[k2]; 
        else
            b[k] = -1;
        return;
    }
    
    if(b[k2]<0){
        if(b[k1]>=0)
            b[k] = b[k1]; 
        else
            b[k] = -1;
        return;
    }
    
    if(____________________) 
        b[k] = b[k1];
    else
        b[k] = b[k2];
}

//对a中数据，输出最大，次大元素位置和值 
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;
        else
            b[n-1+i] = -1;
    }
    
    //从最后一个向前处理
    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]; 
            else
                b[(i-1)/2] = -1;
        }
        else{
            if(a[b[i]]>a[b[i-1]])
                b[(i-1)/2] = b[i];
            else
                b[(i-1)/2] = b[i-1];
        }
    }
    
    //输出树根
    printf("%d:%d\n", b[0], a[b[0]]);
    
    //值等于根元素的需要重新pk
    pk(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,255,30,9,58,66};
    f(a,10);    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

Java

import java.util.*;
public class Main
{
    static void f(int[] a)
    {
        int n = 1;
        while(n<a.length) n *= 2;
        
        
        int[] b = new int[2*n-1];
        for(int i=0; i<n; i++){ 
            if(i<a.length) 
                b[n-1+i] = i;
            else
                b[n-1+i] = -1;
        }
        
        //从最后一个向前处理
        for(int i=b.length-1; i>0; i-=2){
            if(b[i]<0){
                if(b[i-1]>=0)
                    b[(i-1)/2] = b[i-1]; 
                else
                    b[(i-1)/2] = -1;
            }
            else{
                if(a[b[i]]>a[b[i-1]])
                    b[(i-1)/2] = b[i];
                else
                    b[(i-1)/2] = b[i-1];
            }
        }
        
        //输出树根
        System.out.println(b[0] + ":" + a[b[0]]);
        
        //值等于根元素的需要重新pk
        pk(a,b,0,b[0]);
        
        //再次输出树根
        System.out.println(b[0] + ":" + a[b[0]]);
    }
    
    static void pk(int[] a, int[] b, int k, int v)
    {
        //if(k>b.length) return;
        
        int k1 = k*2+1;
        int k2 = k1 + 1;
        
        if(k1>=b.length || k2>=b.length){
            b[k] = -1;
            return;
        }
        
        if(b[k1]==v) 
            pk(a,b,k1,v);
        else
            pk(a,b,k2,v);
        
        
        //重新比较
        if(b[k1]<0){
            if(b[k2]>=0)
                b[k] = b[k2]; 
            else
                b[k] = -1;
            return;
        }
        
        if(b[k2]<0){
            if(b[k1]>=0)
                b[k] = b[k1]; 
            else
                b[k] = -1;
            return;
        }
        
        if(_________________)
            b[k] = b[k1];
        else
            b[k] = b[k2];
    }
    
    public static void main(String[] args)
    {
        int[] a = {54,55,18,16,122,255,30,9,58,66};
        f(a);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

问题分析
C语言程序填入“a[b[k1]]>a[b[k2]]”
Java语言程序同样填入“a[b[k1]] > a[b[k2]]”

AC的C语言程序如下：

#include 
#include 

//重新决出k号位置，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);
    else
        pk(a,b,n,k2,v);
    
    //重新比较
    if(b[k1]<0){
        if(b[k2]>=0)
            b[k] = b[k2]; 
        else
            b[k] = -1;
        return;
    }
    
    if(b[k2]<0){
        if(b[k1]>=0)
            b[k] = b[k1]; 
        else
            b[k] = -1;
        return;
    }
    
    if(a[b[k1]]>a[b[k2]]) 
        b[k] = b[k1];
    else
        b[k] = b[k2];
}

//对a中数据，输出最大，次大元素位置和值 
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;
        else
            b[n-1+i] = -1;
    }
    
    //从最后一个向前处理
    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]; 
            else
                b[(i-1)/2] = -1;
        }
        else{
            if(a[b[i]]>a[b[i-1]])
                b[(i-1)/2] = b[i];
            else
                b[(i-1)/2] = b[i-1];
        }
    }
    
    //输出树根
    printf("%d:%d\n", b[0], a[b[0]]);
    
    //值等于根元素的需要重新pk
    pk(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,255,30,9,58,66};
    f(a,10);    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

AC的Java语言程序如下：

import java.util.*;
public class Main
{
    static void f(int[] a)
    {
        int n = 1;
        while(n<a.length) n *= 2;
        
        
        int[] b = new int[2*n-1];
        for(int i=0; i<n; i++){ 
            if(i<a.length) 
                b[n-1+i] = i;
            else
                b[n-1+i] = -1;
        }
        
        //从最后一个向前处理
        for(int i=b.length-1; i>0; i-=2){
            if(b[i]<0){
                if(b[i-1]>=0)
                    b[(i-1)/2] = b[i-1]; 
                else
                    b[(i-1)/2] = -1;
            }
            else{
                if(a[b[i]]>a[b[i-1]])
                    b[(i-1)/2] = b[i];
                else
                    b[(i-1)/2] = b[i-1];
            }
        }
        
        //输出树根
        System.out.println(b[0] + ":" + a[b[0]]);
        
        //值等于根元素的需要重新pk
        pk(a,b,0,b[0]);
        
        //再次输出树根
        System.out.println(b[0] + ":" + a[b[0]]);
    }
    
    static void pk(int[] a, int[] b, int k, int v)
    {
        //if(k>b.length) return;
        
        int k1 = k*2+1;
        int k2 = k1 + 1;
        
        if(k1>=b.length || k2>=b.length){
            b[k] = -1;
            return;
        }
        
        if(b[k1]==v) 
            pk(a,b,k1,v);
        else
            pk(a,b,k2,v);
        
        
        //重新比较
        if(b[k1]<0){
            if(b[k2]>=0)
                b[k] = b[k2]; 
            else
                b[k] = -1;
            return;
        }
        
        if(b[k2]<0){
            if(b[k1]>=0)
                b[k] = b[k1]; 
            else
                b[k] = -1;
            return;
        }
        
        if(a[b[k1]] > a[b[k2]])
            b[k] = b[k1];
        else
            b[k] = b[k2];
    }
    
    public static void main(String[] args)
    {
        int[] a = {54,55,18,16,122,255,30,9,58,66};
        f(a);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90