洛谷 P2678 [NOIP 2015 提高组] 跳石头

// P2678 跳石头 —— ★ 这一版就能 AC
//
// 「移走至多 M 块石头，使**最短跳跃距离尽可能长**」——「最小值最大」，
// 和本章正文那道「最大值最小」（P1182）是**镜像**的：
//
//     P1182：ok(x) = 「每段不超过 x」能切成 <= M 段吗   x 越大越容易 ⇒ 找第一个 ✓
//     P2678：ok(x) = 「每一跳都 >= x」要移走 <= M 块吗   x 越大越难   ⇒ 找最后一个 ✓
//
// ⚠ 方向反了 ⇒ 二分的两条分支也跟着反：
//     可行 → lo = mid（答案在右边，mid 自己也算）   不可行 → hi = mid − 1
//   ★ 这时 mid 必须**上取整** `mid = lo + (hi - lo + 1) / 2`，否则 lo == hi−1 时死循环
//     （第 8 章第 ⑥ 步那个坑的镜像版）。
//
// ok(x) 的贪心：从起点往右扫，够不到 x 就把这块移走；
// ⚠ **最后那一跳到终点也得数** —— 忘了它就是最常见的那个 WA（见 p2678NoEnd.cpp）。
//
// 上下界：lo = 0（M = N 时把石头全移走，答案是 L；但下界取 0 最稳），hi = **L**
//   —— ⚠ 不是 max(D_i)：石头全移走之后那一跳的长度就是 L（见 p2678HiMax.cpp）。

#include <bits/stdc++.h>
using namespace std;

static int n, m;
static long long L;
static vector<long long> d;

/** 每一跳都 >= x 的话，至少要移走几块 */
static int need(long long x) {
    int cnt = 0;
    long long last = 0;
    for (int i = 0; i < n; i++) {
        if (d[i] - last < x) cnt++;          // 够不到 ⇒ 这块移走
        else last = d[i];
    }
    if (L - last < x) cnt++;                 // ★ 终点那一跳也得够
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> L >> n >> m)) return 0;
    d.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> d[i];

    long long lo = 0, hi = L;
    while (lo < hi) {
        long long mid = lo + (hi - lo + 1) / 2;   // ★ 上取整
        if (need(mid) <= m) lo = mid;             // 可行 ⇒ 还能更长
        else hi = mid - 1;
    }
    cout << lo << '\n';
    return 0;
}

// ⚠ 最常见的那个 WA：ok() 里忘了**终点那一跳**
//
//     if (L - last < x) cnt++;      ← 删掉了
//
// 为什么容易忘：题面说的是「起点 → 石头 → …… → 终点」，
// 而循环是照着**石头**写的 —— 终点不是石头，它不在那个数组里。
// ⇒ **凡是「最后一段 / 最后一跳」不在数组里的题，都要单独补一句。**
//
// ★ 它错的方向是**偏大**：少数了一次「要移走的石头」，于是某些其实不可行的 x
//   被判成可行，二分往右多走了一段。

#include <bits/stdc++.h>
using namespace std;

static int n, m;
static long long L;
static vector<long long> d;

static int need(long long x) {
    int cnt = 0;
    long long last = 0;
    for (int i = 0; i < n; i++) {
        if (d[i] - last < x) cnt++;
        else last = d[i];
    }
    return cnt;                                   // ⚠ 少了终点那一跳
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> L >> n >> m)) return 0;
    d.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> d[i];
    long long lo = 0, hi = L;
    while (lo < hi) {
        long long mid = lo + (hi - lo + 1) / 2;
        if (need(mid) <= m) lo = mid;
        else hi = mid - 1;
    }
    cout << lo << '\n';
    return 0;
}

// ⚠ 只改一处：上界写成 max(D_i)，不是 L
//
//     long long hi = d[n-1];      ← 本来是 L
//
// 想法是「最长的一跳总不会超过最远那块石头吧」—— ⚠ 会的：
// 把石头**全部**移走（M = N 时允许）之后，唯一的一跳就是起点直接到终点，长度 **L**，
// 而 L > D_i 对每块石头都成立（题面：`0 < D_i < L`）。
//
// ⇒ 这个错和 p1182LoAvg.cpp 正好凑成一对：
//   **下界只要 <= 答案就安全，上界只要 >= 答案就安全** ——
//   出事的从来不是「松」，是「没包住」。

#include <bits/stdc++.h>
using namespace std;

static int n, m;
static long long L;
static vector<long long> d;

static int need(long long x) {
    int cnt = 0;
    long long last = 0;
    for (int i = 0; i < n; i++) {
        if (d[i] - last < x) cnt++;
        else last = d[i];
    }
    if (L - last < x) cnt++;
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> L >> n >> m)) return 0;
    d.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> d[i];
    long long lo = 0, hi = n ? d[n - 1] : L;      // ⚠ 就是这一行
    while (lo < hi) {
        long long mid = lo + (hi - lo + 1) / 2;
        if (need(mid) <= m) lo = mid;
        else hi = mid - 1;
    }
    cout << lo << '\n';
    return 0;
}

// ⚠ 只改一处：判定写成 `need(mid) < m`，少了个等号
//
//     if (need(mid) < m) lo = mid;      ← 本来是 <= m
//
// 题面：「**至多**移走 M 块」—— 正好移走 M 块是**允许**的。
// 少个等号就等于把「正好用满预算」的方案全部作废，答案偏小。
//
// ⚠ 这里原来写的是「它只在『最优方案恰好要移走 M 块』时才现形，随机数据抓不到」——
//   **实测打脸：随机档 400 轮就抓到 318 次。**
//   道理很直白：`m = 0` 时 `need(mid) < 0` 永远不成立，它直接输出 0；
//   而 `m > 0` 时只要最优方案用满了预算就现形，这在小数据里很常见。
//   ⇒ **「这个 bug 很难抓」也是一句要先量再说的话**，别拿直觉当结论。

#include <bits/stdc++.h>
using namespace std;

static int n, m;
static long long L;
static vector<long long> d;

static int need(long long x) {
    int cnt = 0;
    long long last = 0;
    for (int i = 0; i < n; i++) {
        if (d[i] - last < x) cnt++;
        else last = d[i];
    }
    if (L - last < x) cnt++;
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> L >> n >> m)) return 0;
    d.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> d[i];
    long long lo = 0, hi = L;
    while (lo < hi) {
        long long mid = lo + (hi - lo + 1) / 2;
        if (need(mid) < m) lo = mid;              // ⚠ 少了等号
        else hi = mid - 1;
    }
    cout << lo << '\n';
    return 0;
}

// P2678 的暴力：枚举「移走哪几块」，取最短跳跃距离的最大值
//
// 石头只有 n 块，每块「移 / 不移」⇒ 2ⁿ 种方案；对每种方案算一遍最短跳。
// ⇒ O(2ⁿ × n)，n = 20 就要一千万次，**满数据 n = 5×10⁴ 想都别想**。
//
// ★ 它的用处只有一个：**当对拍的参照物**。
//   它和二分那版**没有任何共用逻辑** —— 一个在枚举方案，一个在枚举答案，
//   两边一起错的概率极低（第 7 章 P1147 那条：验算要走一条无关的路）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long L;
    int n, m;
    if (!(cin >> L >> n >> m)) return 0;
    vector<long long> d(n);
    for (int i = 0; i < n; i++) cin >> d[i];

    long long best = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        if (__builtin_popcount((unsigned)mask) > m) continue;   // 至多移走 m 块
        long long last = 0, mn = LLONG_MAX;
        for (int i = 0; i < n; i++) {
            if (mask >> i & 1) continue;                        // 这块被移走了
            mn = min(mn, d[i] - last);
            last = d[i];
        }
        mn = min(mn, L - last);                                 // 终点那一跳
        best = max(best, mn);
    }
    cout << best << '\n';
    return 0;
}

// 数据生成器（P2678 对拍用）：`./p2678Gen <seed> [level]`
//
//   level 0（默认）随机小数据：n <= 10、L <= 40、m ∈ [0, n]
//   level 1        ★ **石头挤在终点那一侧**：位置集中在 [3L/4, L−1] —— 逼出「终点那一跳」。
//                  ⚠ 这个档位一开始造反了：第一版挤在 **[1, L/4]**（左边），
//                    结果对 p2678NoEnd 是**精确的 0**（400 轮一次没抓到）——
//                    石头挤在左边，最后一块离终点**很远**，`L − last` 绰绰有余，
//                    那句话删不删都一样。**要让最后一跳变短，石头就得挤在右边。**
//   level 2        **预算刚好用光**：先随机造，再把 m 调成「最优解正好要移走的块数」
//   level 3        ⚠ **对照档：石头挤在起点侧**（[1, L/4]）—— 故意留着的**反面教材**。
//                  它是「level 1 造反了的那一版」，对 p2678NoEnd 是**精确的 0**。
//                  留着它是为了把「方向搞反的档位长什么样」钉成一条断言：
//                  **看到一个精确的 0，先问「我这一档到底逼紧了哪一头」。**
//
// ⚠ n <= 10 是为了让 p2678Brute 的 2ⁿ 跑得动（它是对拍的参照物）。

#include <bits/stdc++.h>
using namespace std;
static mt19937 rng;
static int ri(int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); }

/** 至多移走 m 块时的答案（照 p2678Brute 那套枚举，生成器自己也要会算） */
static long long best(long long L, vector<long long>& d, int m) {
    int n = (int)d.size();
    long long b = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        if (__builtin_popcount((unsigned)mask) > m) continue;
        long long last = 0, mn = LLONG_MAX;
        for (int i = 0; i < n; i++) { if (mask >> i & 1) continue; mn = min(mn, d[i] - last); last = d[i]; }
        b = max(b, min(mn, L - last));
    }
    return b;
}

int main(int argc, char** argv) {
    rng.seed((argc > 1) ? (unsigned)atoi(argv[1]) : 1);
    int level = (argc > 2) ? atoi(argv[2]) : 0;

    int n = ri(1, 10);
    long long L = ri(n + 1, 40);
    set<long long> pos;
    while ((int)pos.size() < n) {
        long long lo = (level == 1) ? max<long long>(1, L * 3 / 4) : 1;
        long long hi = (level == 3) ? max<long long>(1, L / 4) : L - 1;
        if (lo > hi) lo = 1;
        pos.insert(ri((int)lo, (int)hi));
        if ((int)pos.size() < n && (int)(hi - lo + 1) < n) n = (int)(hi - lo + 1);   // 位置不够放，缩 n
    }
    vector<long long> d(pos.begin(), pos.end());
    n = (int)d.size();

    int m;
    if (level == 2) {
        /* 预算刚好用光：答案在 m 和 m−1 之间真的会变，说明第 m 块非移不可 */
        m = ri(1, n);
        while (m > 1 && best(L, d, m) == best(L, d, m - 1)) m--;
    } else {
        m = ri(0, n);
    }
    printf("%lld %d %d\n", L, n, m);
    for (int i = 0; i < n; i++) printf("%lld\n", d[i]);
    return 0;
}

// 换一把尺子：三条路各要做多少次
//
// 用法：./p2678Count <L> <n> <m>          人话版
//       ./p2678Count <L> <n> <m> csv      只打 `键,值`，给 check:viz 用
//
// 这道题的三条路，代价的**来源完全不同**：
//   ① 枚举「移走哪几块」（p2678Brute 那一版）：2ⁿ 种方案 —— 由 **n** 决定
//   ② 枚举答案，从 L 往下一个个试：最多 L + 1 次 —— 由 **L** 决定，和 n 无关
//   ③ 二分答案：⌊log2(L)⌋ + 1 次判定，每次 O(n)
//
// ★ 值得单独记一句：① 和 ② **都是「暴力」，但它们慢在完全不同的地方**。
//   n 小 L 大时 ① 反而更快，n 大 L 小时 ② 更快 ——
//   「暴力有多慢」这句话不写清楚**枚举的是什么**，就是没说。

#include <bits/stdc++.h>
using namespace std;

static int n, m;
static long long L;
static vector<long long> d;
static long long calls;

static int need(long long x) {
    calls++;
    int cnt = 0;
    long long last = 0;
    for (int i = 0; i < n; i++) {
        if (d[i] - last < x) cnt++;
        else last = d[i];
    }
    if (L - last < x) cnt++;
    return cnt;
}

int main(int argc, char** argv) {
    L = (argc > 1) ? atoll(argv[1]) : 1000000000LL;
    n = (argc > 2) ? atoi(argv[2]) : 50000;
    m = (argc > 3) ? atoi(argv[3]) : 25000;
    bool csv = (argc > 4 && string(argv[4]) == "csv");

    mt19937_64 rng(20260827ull);
    set<long long> s;
    while ((int)s.size() < n) s.insert((long long)(rng() % (unsigned long long)(L - 1)) + 1);
    d.assign(s.begin(), s.end());
    n = (int)d.size();

    calls = 0;
    long long lo = 0, hi = L;
    while (lo < hi) {
        long long mid = lo + (hi - lo + 1) / 2;
        if (need(mid) <= m) lo = mid; else hi = mid - 1;
    }
    long long binCalls = calls;
    long long ans = lo;

    long long enumAns = L - ans + 1;                 // ② 从 L 往下试到答案，要试几次
    int lg = 0; for (long long x = L; x > 0; x >>= 1) lg++;

    if (csv) {
        printf("L,%lld\nn,%d\nm,%d\nanswer,%lld\n", L, n, m, ans);
        printf("binCalls,%lld\nlog2L,%d\nenumFromL,%lld\n", binCalls, lg, enumAns);
        printf("binOps,%lld\nenumOps,%lld\n", binCalls * n, enumAns * n);
        printf("ratio,%lld\n", enumAns / max(1LL, binCalls));
        return 0;
    }
    printf("L = %lld、n = %d、m = %d ⇒ 答案 = %lld\n\n", L, n, m, ans);
    printf("  ② 枚举答案（从 L 往下一个个试）  %12lld 次判定\n", enumAns);
    printf("  ③ 二分答案                      %12lld 次判定（⌊log2 L⌋+1 = %d）\n", binCalls, lg);
    printf("\n  差 %lld 倍。每次判定都是 O(n) = %d 步，所以总步数差的也是这个倍数。\n",
           enumAns / max(1LL, binCalls), n);
    printf("\n  ① 枚举「移走哪几块」是 2^%d 种方案 —— 它和 L 无关，只和 n 有关，\n", n);
    printf("     n 到 %d 就已经是天文数字了。**两种暴力慢在完全不同的地方。**\n", n);
    return 0;
}

// 顶格数据（P2678 计时用）：`./p2678GenBig <L> <n> <m> [level]`
//
//   level 0（默认）石头位置在 [1, L−1] 里随机取 n 个不重复的
//   level 1        **等间距**：最短跳固定 —— 用来看「答案落在哪儿」而不是「跑多久」
//
// ⚠ 题面：0 <= M <= N <= 5×10⁴、1 <= L <= 10⁹、0 < D_i < L 且两两不同、按升序给出。
//   ⇒ 位置必须**去重 + 排序**，否则造出来的不是这道题的数据。

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
    long long L = (argc > 1) ? atoll(argv[1]) : 1000000000LL;
    int n = (argc > 2) ? atoi(argv[2]) : 50000;
    int m = (argc > 3) ? atoi(argv[3]) : 25000;
    int level = (argc > 4) ? atoi(argv[4]) : 0;

    vector<long long> d;
    if (level == 1) {
        for (int i = 1; i <= n; i++) d.push_back(L * i / (n + 1));
    } else {
        mt19937_64 rng(20260827ull);
        set<long long> s;
        while ((int)s.size() < n) s.insert((long long)(rng() % (unsigned long long)(L - 1)) + 1);
        d.assign(s.begin(), s.end());
    }
    sort(d.begin(), d.end());
    d.erase(unique(d.begin(), d.end()), d.end());
    n = (int)d.size();
    if (m > n) m = n;

    printf("%lld %d %d\n", L, n, m);
    for (int i = 0; i < n; i++) printf("%lld\n", d[i]);
    return 0;
}