NOIP 2007 普及組「紀念品分組」題解：貪心雙指針最小分組數

NOIP 2007 普及組「紀念品分組」題解：貪心雙指針最小分組數

題目大意

有 n 件紀念品，每件價格 p_i。每組最多兩件，組內價格和 ≤ w。求最少分組數。

範例：
w=100, n=9, prices=[90,20,20,30,50,60,70,80,90] → 最少 6 組。

貪心策略證明

將價格排序後，用雙指針 l (最小) 和 r (最大)：

• 若 a[l] + a[r] ≤ w：最小與最大配對，l++、r--、組數 ++。
• 否則：最大無法與任何人配對（因最小都超標），最大單獨成組，r--、組數 ++。

此策略保證每組盡可能裝兩件，全域最優。

完整代碼 (C 語言)

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

long long a[30010];

// 快速排序
void qsort_ll(int l, int r) {
    if (l >= r) return;
    int i = l, j = r;
    long long mid = a[(l + r) >> 1];
    do {
        while (a[i] < mid) i++;
        while (a[j] > mid) j--;
        if (i <= j) {
            long long t = a[i]; a[i] = a[j]; a[j] = t;
            i++; j--;
        }
    } while (i <= j);
    if (l < j) qsort_ll(l, j);
    if (i < r) qsort_ll(i, r);
}

int main() {
    long long w, n;
    scanf("%lld%lld", &w, &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    qsort_ll(1, n);

    int l = 1, r = n, groups = 0;
    while (l <= r) {
        if (a[l] + a[r] <= w) l++;  // 配對成功
        r--;                         // 最大者必進組
        groups++;
    }
    printf("%d\n", groups);
    return 0;
}

複雜度分析

• 排序：O(n log n)
• 雙指針掃描：O(n)
• 空間：O(n)

關鍵細節

1. 題目保證 5 ≤ p_i ≤ w，單件永遠不超標。
2. 使用 long long 防止價格和溢位（雖然 w 通常在 int 範圍）。
3. 快排實現採用標準 Hoare 分區，遞歸深度 log n 安全。

舉一反三

同類「雙指針配對」問題：
• 救生艇載人、
• 兩數之和不超限最大配對數、
• 會議室安排最少房間數（區間重疊）。