Codeforces 479D Long Jumps - 貪心 + 二分查找最少添加刻度

問題描述

尺子長度 L，現有 N 個刻度 (N ≤ 10⁵)。女生標準 x，男生標準 y。可添加刻度。求最少添加幾個刻度，使能測量出距離 x 和 y (即存在兩刻度差為 x，且存在兩刻度差為 y)。輸出添加數量及具體位置 (任意合法方案)。

關鍵觀察：答案 ≤ 2

最多添加 x 和 y 兩個刻度即可滿足。故只需判斷：0 個、1 個、2 個 三種情況。

算法流程

1. 讀入刻度數組 a[]，排序 (輸入已保證遞增)。
2. 定義函數 has(d)：二分查找是否存在差為 d 的刻度對。對每個 a[i]，查 a[i]+d 是否存在 (或 a[i]-d)。
3. 檢查 has(x) 和 has(y)：
   • 均 true → 輸出 0。
   • 只有 x 缺 → 輸出 1 和位置 x (或任意可測 x 的位置)。
   • 只有 y 缺 → 輸出 1 和位置 y。
   • 均缺 → 嘗試添加 1 個刻度同時滿足 x 和 y。

添加 1 個刻度同時滿足 x 和 y 的判斷

枚舉現有刻度 a[i] 作為參考，嘗試在 a[i] ± x 或 a[i] ± y 添加新刻度 pos，檢查新刻度與現有刻度能否構成另一距離。具體：

• 候選位置：a[i] + x, a[i] - x, a[i] + y, a[i] - y (需在 [0, L] 內)。
• 對每個候選 pos，檢查 has(pos ± x) 或 has(pos ± y) (排除自身)。
• 若存在，輸出 1 和 pos。

參考代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;

int a[MAXN];
int n, L, x, y;

bool has(int val) {
    if (val < 0 || val > L) return false;
    int idx = lower_bound(a, a+n, val) - a;
    return idx < n && a[idx] == val;
}

int main() {
    scanf("%d%d%d%d", &n, &L, &x, &y);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    bool hx = false, hy = false;
    for (int i = 0; i < n; i++) {
        if (has(a[i] + x) || has(a[i] - x)) hx = true;
        if (has(a[i] + y) || has(a[i] - y)) hy = true;
    }

    if (hx && hy) { puts("0"); return 0; }
    if (hx) { puts("1"); printf("%d\n", y); return 0; }
    if (hy) { puts("1"); printf("%d\n", x); return 0; }

    // 嘗試加 1 個
    for (int i = 0; i < n; i++) {
        // 以 a[i] 為基準加 x
        int pos = a[i] + x;
        if (pos <= L && (has(pos - y) || has(pos + y))) {
            puts("1"); printf("%d\n", pos); return 0;
        }
        pos = a[i] - x;
        if (pos >= 0 && (has(pos - y) || has(pos + y))) {
            puts("1"); printf("%d\n", pos); return 0;
        }
        // 以 a[i] 為基準加 y
        pos = a[i] + y;
        if (pos <= L && (has(pos - x) || has(pos + x))) {
            puts("1"); printf("%d\n", pos); return 0;
        }
        pos = a[i] - y;
        if (pos >= 0 && (has(pos - x) || has(pos + x))) {
            puts("1"); printf("%d\n", pos); return 0;
        }
    }

    // 必須加 2 個
    puts("2");
    printf("%d %d\n", x, y);
    return 0;
}

複雜度

• 預處理：無 (輸入已排序)。
• 檢查 hx/hy：O(N log N)。
• 枚舉候選位置：O(N log N) (每個候選 O(log N) 二分)。
• 總 O(N log N)，N=10⁵ 極快。

易錯點

• 候選位置需檢查邊界 [0, L]。
• has 函數需用 lower_bound 精確匹配，不可用 binary_search 直接判斷 (需確認存在)。
• 添加 2 個時輸出 x 和 y 任意順序均可。