SOJ 3102 第 K 小數：O(n) 選擇算法與 nth_element 實戰

問題描述

給定 n (≤ 2,000,000) 個整數，求第 k 小的數。多測試用例，輸入規模大，需快速 IO 和 O(n) 算法。

算法選擇對比

STL nth_element 實戰 (推薦)

#include 
#include 
#include 
using namespace std;

const int MAXN = 2000005;
int a[MAXN];

// 快速輸入
inline bool readInt(int& x) {
    int c = getchar();
    if (c == EOF) return false;
    while (c <= ' ') c = getchar();
    bool neg = false;
    if (c == '-') { neg = true; c = getchar(); }
    x = 0;
    while (c >= '0') { x = x * 10 + c - '0'; c = getchar(); }
    if (neg) x = -x;
    return true;
}

int main() {
    int n, k;
    while (readInt(n) && readInt(k)) {
        for (int i = 0; i < n; ++i) readInt(a[i]);
        nth_element(a, a + k - 1, a + n);
        printf("%d\n", a[k-1]);
    }
    return 0;
}

手寫快速選擇 (避免 STL 開銷)

int quickSelect(int* a, int l, int r, int k) {  // 0-based, 求第 k 小 (k 從 0 開始)
    while (l < r) {
        int pivot = a[l + rand() % (r - l + 1)];
        int i = l, j = r;
        while (i <= j) {
            while (a[i] < pivot) ++i;
            while (a[j] > pivot) --j;
            if (i <= j) swap(a[i++], a[j--]);
        }
        if (k <= j) r = j;
        else if (k >= i) l = i;
        else return a[k];
    }
    return a[l];
}

關鍵優化點

1. 快速 IO：`getchar()` 手寫解析，避免 `scanf`/`cin` 慢
2. 隨機 pivot：`rand()` 防止有序數據退化
3. 原地分區：雙指針交換，O(1) 空間
4. 迭代而非遞歸：避免棧溢出，尾遞歸優化為循環

位運算快速解析整數 (極致優化)

inline int fastRead() {
    int c, x = 0;
    do c = getchar(); while (c <= ' ');
    bool neg = false;
    if (c == '-') { neg = true; c = getchar(); }
    for (; c >= '0'; c = getchar()) x = (x << 3) + (x << 1) + (c - '0');  // x*10
    return neg ? -x : x;
}

`(x<<3)+(x<<1)` 等價 `x*10`，無乘法指令，極快。

測試數據規模應對

• n=2,000,000，數組約 8MB，靜態分配安全
• 多測試用例累計 n 可能更大，每次複用數組
• 時間限制嚴格時：`nth_element` 可能比手寫快選更快 (Intel 編譯器優化)