UVA 11714 - Blind Sorting (推理 + 公式)

問題描述

n 個不同數，每次比較兩個大小。最壞情況下，至少需要多少次比較才能找出最大和第二大兩個數？

推理過程

1. 用淘汰賽找最大值：n-1 次比較，形成比較樹，最大值在根，葉為原始數。
2. 第二大必須是直接輸給最大值的數中的最大者。最大值進行了 ⌈log₂ n⌉ 輪比較（樹高），故有 ⌈log₂ n⌉ 個直接對手。
3. 在這 ⌈log₂ n⌉ 個數中找最大，需 ⌈log₂ n⌉ - 1 次比較。
4. 總比較次數 = (n-1) + (⌈log₂ n⌉ - 1) = n + ⌈log₂ n⌉ - 2。

公式

ans = n + ceil(log2(n)) - 2

完整代碼

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    while(cin>>n) {
        cout << n + (int)ceil(log2((double)n)) - 2 << endl;
    }
    return 0;
}

驗證

• n=2: 2+1-2=1 (比較一次得最大和第二大)
• n=3: 3+2-2=3 (淘汰賽 2 次 + 1 次)
• n=4: 4+2-2=4