首页 > 代码库 > UVA11714 - Blind Sorting(推理)

UVA11714 - Blind Sorting(推理)

题目链接


题意:给出n个数,求出得到最大数和第二大数所用的最多的比较次数

思路:可以取两个数两两做比较,就相当与建立二叉树,两个数的最大值就相当与两个的父节点,所以我们我们可以知道得到最大值时的比较次数为n-1,然后假设所有左儿子都大于右儿子,所以最大值的右儿子还有跟左子树中的值做比较得到第二大数,比较的个数为树高。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

int n;

int main() {
    while (scanf("%d", &n) != EOF) {
        int ans = n - 1 + (int)(ceil(log(n) / log(2))) - 1;
        printf("%d\n", ans); 
    }    
    return 0;
}