NYOJ 86 找球號 排序 + 二分查找

NYOJ 86 找球號 (一) 題目解析

m (≤100,000) 個球，每球有編號 (0~100,000,000)。n (≤1,000,000) 次查詢，每次給編號 k，判斷是否存在。輸出 YES/NO。

算法選擇：排序 + 二分查找

m 較大，線性查找 O(mn) 超時。預處理排序 O(m log m)，每次查詢 O(log m)，總複雜度 O((m+n) log m)。

C 代碼實現

#include <stdio.h>
#include <stdlib.h>

int s[1000005];
int low, high;

int cmp(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int binary_search(int x) {
    int mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (s[mid] == x) return 1;
        else if (s[mid] < x) low = mid + 1;
        else high = mid - 1;
    }
    return 0;
}

int main() {
    int i, m, n, a;
    scanf("%d%d", &m, &n);
    for (i = 0; i < m; i++) scanf("%d", &s[i]);
    qsort(s, m, sizeof(int), cmp);
    while (n--) {
        low = 0; high = m - 1;
        scanf("%d", &a);
        printf(binary_search(a) ? "YES\n" : "NO\n");
    }
    return 0;
}

優化建議

• 使用 std::binary_search 或 std::unordered_set (O(1) 平均查找)
• 輸入量大時用 fast I/O (scanf/printf 或 ios::sync_with_stdio(false))
• 編號範圍 0~1e8，若內存允許可用位圖/布隆過濾器

樣例驗證

輸入：6 4 / 23 34 46 768 343 343 / 2 4 23 343
排序後：23 34 46 343 343 768
查詢：2→NO, 4→NO, 23→YES, 343→YES