UVA11714 - Blind Sorting(推理)

UVA11714 - Blind Sorting(推理)

題目鏈接

題意：給出n個數，求出得到最大數和第二大數所用的最多的比較次數

思路：可以取兩個數兩兩做比較，就相當與建立二叉樹，兩個數的最大值就相當與兩個的父節點，所以我們我們可以知道得到最大值時的比較次數為n-1，然後假設所有左兒子都大於右兒子，所以最大值的右兒子還有跟左子樹中的值做比較得到第二大數，比較的個數為樹高。

代碼：

#include 
#include 
#include 
#include 
#include 

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;
}