P1182 数列分段 Section II · 习题解析｜信息学奥赛算法练功房

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P1182，日期见页头。两边不一致时信原站。

题目描述

对于给定的一个长度为 N 的正整数数列 A₁~ₙ，现要将其分成 M（M ≤ N）段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：例如一数列 4 2 4 5 1 要分成 3 段。

将其如下分段：[4 2][4 5][1] —— 第一段和为 6，第 2 段和为 9，第 3 段和为 1，和最大值为 9。

将其如下分段：[4][2 4][5 1] —— 第一段和为 4，第 2 段和为 6，第 3 段和为 6，和最大值为 6。

并且无论如何分段，最大值不会小于 6。所以可以得到要将数列 4 2 4 5 1 分成 3 段，每段和的最大值最小为 6。

输入格式

第 1 行包含两个正整数 N, M。

第 2 行包含 N 个空格隔开的非负整数 Aᵢ，含义如题目所述。

输出格式

一个正整数，即每段和最大值最小为多少。

说明 / 提示

对于 20% 的数据，N ≤ 10。对于 40% 的数据，N ≤ 1000。

对于 100% 的数据，1 ≤ N ≤ 10⁵，M ≤ N，Aᵢ < 10⁸，答案不超过 10⁹。

输入输出样例

输入

5 3
4 2 4 5 1

输出

就是题面里讲的那组：[4][2 4][5 1] 的最大值 6，比 [4 2][4 5][1] 的 9 小。

1⚠ 这一页不讲怎么做 —— 它是本章原题

★ 这一页只干一件事：把正文那个「上下界」警告框拿去实测

第 9 章整章讲的就是这道题，解法在正文第 ⑥、⑦ 步，这里不重复。

⚠ 但正文第 ⑥ 步末尾那个警告框（「二分的上下界一定要包住答案」）里有几句话，当时是讲道理讲出来的，没有跑过。这一页把它们一句一句做成能跑的程序，量一遍 ——

结果是其中两句不成立，已经把正文改了。（改了什么、为什么，见第 ④ 步。）

⇒ 这也是本书的规矩之一：正文里的每个数字、每个「会怎样」，都得是实测的。 「听起来很有道理」和「跑过」之间，隔着的正是这一页。

2先把能 AC 的那一版摆在这儿

p1182.cpp★ 这一版就能 AC

// P1182 数列分段 Section II —— ★ 这一版就能 AC（也就是本章 fast.cpp 那一版）
//
// 「分成 M 段、每段和的最大值最小」⇒ 二分**答案本身**：
//   ok(x) = 「每段和都不超过 x」时，最少要切成几段，段数 <= M 吗
//   x 越大越容易 ⇒ 可行性单调 ⇒ 二分那条分界线。
//
// 上下界（本章第 ⑥ 步那个警告框说的就是这两行）：
//   lo = max(a_i)   ← **不能更小**：一段至少装得下最大的那个数
//   hi = sum(a_i)   ← 不分段（M = 1）时就是它
//
// ⚠ sum 最大 10⁵ × 10⁸ = 10¹³，**装不进 int**（见 p1182Int.cpp）。

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

static int n, m;
static vector<long long> a;

static bool ok(long long limit) {
    int seg = 1;
    long long cur = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] > limit) return false;          // ★ 单独一个都装不下 ⇒ 这个 limit 不可行
        if (cur + a[i] <= limit) cur += a[i];
        else { seg++; cur = a[i]; }
    }
    return seg <= m;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m)) return 0;
    a.assign(n, 0);
    long long lo = 0, hi = 0;
    for (int i = 0; i < n; i++) { cin >> a[i]; lo = max(lo, a[i]); hi += a[i]; }

    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (ok(mid)) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

顶格数据（n = 10⁵、m = 10⁴、Aᵢ < 10⁸）实测：约 8 毫秒 / 4.7 MB。两个边界写在开头那两行：

lo = max(a_i)     一段至少装得下最大的那个数
hi = sum(a_i)     M = 1 时就是它

下面四个版本，每个只改这两行（或 ok() 里的一行）中的一处。

3四个「只改一处」的版本，命运完全不同

p1182NoBig.cpp① ok() 少一句

// ⚠ 只改一处：ok() 里去掉了「单独一个都装不下」那一句
//
//     if (a[i] > limit) return false;      ← 删掉了
//
// 直觉上这是个 bug：limit 比某个 a[i] 还小时，那一段无论如何都超限，
// 可这一版还是会老老实实「另起一段」，于是它会报告一个**根本不成立**的段数。
//
// ★★★ 但它单独跑**一个字都不会错** —— 因为下界是 `lo = max(a_i)`，
//   二分试到的每一个 mid 都 >= max(a_i)，那句话**永远轮不到执行**。
//   ⇒ 它要和「下界从 1 开始」凑在一起才出事，见 p1182Both.cpp。

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

static int n, m;
static vector<long long> a;

static bool ok(long long limit) {
    int seg = 1;
    long long cur = 0;
    for (int i = 0; i < n; i++) {
        if (cur + a[i] <= limit) cur += a[i];
        else { seg++; cur = a[i]; }
    }
    return seg <= m;
}

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

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

p1182Lo1.cpp② 下界写成 1

// ⚠ 只改一处：下界从 1 开始，不是 max(a_i)
//
//     long long lo = 1;        ← 本来是 max(a_i)
//
// ★★★ 它单独跑也**一个字都不会错** —— 只是多转几轮（多 log(max/1) ≈ 27 轮）。
//   本章第 ⑥ 步那个警告框说的就是这件事：「下界写小了只是浪费几轮」。
//   ⇒ 它要和「ok() 少一句」凑在一起才出事，见 p1182Both.cpp。

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

static int n, m;
static vector<long long> a;

static bool ok(long long limit) {
    int seg = 1;
    long long cur = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] > limit) return false;
        if (cur + a[i] <= limit) cur += a[i];
        else { seg++; cur = a[i]; }
    }
    return seg <= m;
}

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

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

p1182LoAvg.cpp③ 下界写成 sum/m

// ⚠ 只改一处：下界写成「平均值」sum / m —— 本章第 ⑥ 步点名的那个「看着挺聪明」的写法
//
//     long long lo = sum / m;      ← 本来是 max(a_i)
//
// 想法是：分成 m 段，每段平均装 sum/m，答案总不会比平均值还小吧？
// **平均那一半是对的**（答案确实 >= sum/m，因为最大的那段不会小于平均）。
// ⚠ 错的是它**不够大**：答案还必须 >= max(a_i)，
//   而 max(a_i) 完全可以远远超过 sum/m（一个大数 + 一堆小数就是）。
//
// ⇒ 于是二分的范围**从一开始就漏掉了真正的答案**，收敛到一个偏小的值。
// ★ 这一版和 p1182Both.cpp 错得不一样：那一版是 ok() 说了谎，
//   这一版 ok() 一个字没错 —— **是范围本身没包住答案**。

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

static int n, m;
static vector<long long> a;

static bool ok(long long limit) {
    int seg = 1;
    long long cur = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] > limit) return false;
        if (cur + a[i] <= limit) cur += a[i];
        else { seg++; cur = a[i]; }
    }
    return seg <= m;
}

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

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

p1182Both.cpp④ ① 和 ② 一起

// ⚠⚠ 两处**各自无害**的写法凑在一起 —— 这一版是错的
//
//   ① 下界从 1 开始（p1182Lo1.cpp：单独用，只是慢一点，答案对）
//   ② ok() 少了「单独一个都装不下」那一句（p1182NoBig.cpp：单独用，答案也对）
//
// ★★★ 凑在一起就 WA：下界放到 1 之后，二分**真的会试到 mid < max(a_i)**，
//   而这时少了那句判断的 ok() 会说「可行」——
//   它把那个装不下的数**单独切成一段**就交差了，可那一段的和仍然超过 limit。
//   于是二分收敛到一个比真答案**小**的值。
//
// ⇒ 这一页最值钱的一句话：**「这一处改了没事」和「那一处改了没事」，
//   合起来不等于「两处都改了没事」。** 边界条件是成对出现的 ——
//   `lo = max(a_i)` 和 `if (a[i] > limit) return false` 是同一件事的两种写法，
//   删掉任何**一个**都行，两个都删就漏了。

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

static int n, m;
static vector<long long> a;

static bool ok(long long limit) {
    int seg = 1;
    long long cur = 0;
    for (int i = 0; i < n; i++) {
        if (cur + a[i] <= limit) cur += a[i];      // ② 少了那一句
        else { seg++; cur = a[i]; }
    }
    return seg <= m;
}

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

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

生成器三个档位、每档 500 轮，和正解答案不一致的轮数：

p1182Gen.cpp生成器：三个档位

// 数据生成器（P1182 对拍用）：`./p1182Gen <seed> [level]`
//
//   level 0（默认）随机小数据：n <= 8、a_i ∈ [0, 20]、m ∈ [1, n]
//   level 1        **一个数特别大**：其余都很小 —— 冲着「下界 / ok() 那两处边界」去的
//   level 2        **m 贴着 n**：段数几乎不受限，答案就是 max(a_i)
//
// ⚠ 题面允许 a_i = 0（「非负整数」），所以 level 0 的下界取 0 不是笔误。

#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)); }

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, 8), m;
    vector<int> a(n);
    if (level == 1) {
        for (int i = 0; i < n; i++) a[i] = ri(0, 3);
        a[ri(0, n - 1)] = ri(50, 200);              // 一个特别大的
        m = ri(1, n);
    } else if (level == 2) {
        for (int i = 0; i < n; i++) a[i] = ri(0, 20);
        m = ri(max(1, n - 1), n);                   // m 贴着 n
    } else {
        for (int i = 0; i < n; i++) a[i] = ri(0, 20);
        m = ri(1, n);
    }
    printf("%d %d\n", n, m);
    for (int i = 0; i < n; i++) printf("%d%c", a[i], i + 1 == n ? '\n' : ' ');
    return 0;
}

点一下即可编辑

输出

点「运行 ▶」看结果

档位	② `Lo1`	④ `Both`
`level 0` 随机	4	157
`level 1` 一个数特别大	0	283
`level 2` `m` 贴着 `n`	4	324

4★★★ 正文那个警告框里，有两句是错的

⚠ 错的第一句：「下界写成 0 或 1？可以，只是浪费几轮」

写成 0 可以，写成 1 会 WA。

题面写的是「非负整数 Aᵢ」—— Aᵢ 可以是 0。整个数列全是 0 时，答案就是 0，而 lo = 1 把答案排除在二分范围之外了，输出 1。

★ 这个失效条件是双向的，两头都验过： 1500 轮里 Lo1 失效 14 次，14 次全是「整个数列都是 0」；反过来构造的 10 组全 0 数据，10 组全部失效。

⇒ lo = 1 不是「浪费几轮」，是范围没包住答案。这两件事完全不同。

⚠ 错的第二句：「下界写成 sum / m？危险 —— 万一某个数比它还大」

方向反了 —— sum / m 恒安全，1500 轮一次没错过。

那句话的担心是：「某个 Aᵢ 比平均值还大，答案就在范围外面了」。可某个数比平均值大，只会让答案更大：答案 ≥ max(Aᵢ) > sum/m，仍然在 [sum/m, sum] 里。

★ 而且它恒安全有一句话就能说清的理由（鸽巢原理）：把 sum 分成 m 段，最大的那段不可能小于平均值 ⇒ 答案 ≥ sum/m 永远成立。

⇒ 一般化：下界只要 ≤ 答案就安全，上界只要 ≥ 答案就安全。 出事的从来不是「松」或「紧」，是「没包住」。 lo = 1 出事不是因为它松，是因为它 > 0；sum/m 没事不是因为它紧，是因为它 ≤ 答案。

5★ 那「放宽范围要多花几轮」到底是几轮？—— 0 轮

正文那句「拿不准就把范围放宽，log 的代价小到可以忽略」是对的。但「可以忽略」是多少？量一遍：

p1182Count.cpp数轮数

// 换一把尺子：三种下界各要二分多少轮，以及暴力枚举答案要试多少次
//
// 用法：./p1182Count <n> <m>          人话版
//       ./p1182Count <n> <m> csv      只打 `键,值`，给 check:viz 用
//
// 本章第 ⑥ 步那个警告框说「下界写小了只是浪费几轮」——「几轮」是多少？这里量出来。
// 三种下界：
//   ① max(a_i)      正解用的（最紧）
//   ② sum / m       「平均值」—— ★ 它其实也**恒安全**（鸽巢：m 段的最大值 >= 平均值）
//   ③ 1             最松的那种写法
//
// ⚠ 而「浪费几轮」和「安不安全」是两件事：③ 在**全是 0** 的数据上会直接错
//   （答案是 0，而它从 1 起步 —— 见 p1182Lo1.cpp）。
//
// 对照：暴力从 lo 一个一个往上试，要试 (答案 − lo + 1) 次。

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

static int n, m;
static vector<long long> a;

static bool ok(long long limit) {
    int seg = 1;
    long long cur = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] > limit) return false;
        if (cur + a[i] <= limit) cur += a[i];
        else { seg++; cur = a[i]; }
    }
    return seg <= m;
}

/** 从 [lo, hi] 二分，返回 (答案, 转了几轮) */
static pair<long long, int> solve(long long lo, long long hi) {
    int rounds = 0;
    while (lo < hi) { rounds++; long long mid = lo + (hi - lo) / 2; if (ok(mid)) hi = mid; else lo = mid + 1; }
    return { lo, rounds };
}

int main(int argc, char** argv) {
    n = (argc > 1) ? atoi(argv[1]) : 100000;
    m = (argc > 2) ? atoi(argv[2]) : 10000;
    bool csv = (argc > 3 && string(argv[3]) == "csv");

    mt19937 rng(20260827u);
    a.assign(n, 0);
    long long sum = 0, mx = 0;
    for (int i = 0; i < n; i++) { a[i] = (long long)(rng() % 100000000u); sum += a[i]; mx = max(mx, a[i]); }

    auto rMax = solve(mx, sum);
    auto rAvg = solve(sum / m, sum);
    auto rOne = solve(1, sum);

    long long ans = rMax.first;
    long long bruteFromMax = ans - mx + 1;          // 暴力从 max 一个个往上试

    if (csv) {
        printf("n,%d\nm,%d\n", n, m);
        printf("answer,%lld\nsum,%lld\nmaxA,%lld\navg,%lld\n", ans, sum, mx, sum / m);
        printf("roundsMax,%d\nroundsAvg,%d\nroundsOne,%d\n", rMax.second, rAvg.second, rOne.second);
        printf("sameAns,%d\n", (rMax.first == rAvg.first && rAvg.first == rOne.first) ? 1 : 0);
        printf("bruteFromMax,%lld\n", bruteFromMax);
        printf("avgGeqMax,%d\n", (sum / m >= mx) ? 1 : 0);
        return 0;
    }
    printf("n = %d、m = %d：sum = %lld，max = %lld，sum/m = %lld，答案 = %lld\n\n", n, m, sum, mx, sum / m, ans);
    printf("  下界 max(a_i) = %-12lld 二分 %2d 轮\n", mx, rMax.second);
    printf("  下界 sum/m    = %-12lld 二分 %2d 轮\n", sum / m, rAvg.second);
    printf("  下界 1                     二分 %2d 轮\n", rOne.second);
    printf("\n  三者答案%s。\n", (rMax.first == rAvg.first && rAvg.first == rOne.first) ? "完全一致" : "居然不一致！");
    printf("  ⇒ 「下界写小了只是浪费几轮」在这道题上是：最松和最紧差 %d 轮。\n",
           rOne.second - rMax.second);
    printf("\n  对照：暴力从 max 一个一个往上试要 %lld 次 —— 二分只要 %d 次。\n", bruteFromMax, rMax.second);
    return 0;
}

点一下即可编辑

输出

点「运行 ▶」看结果

下界	值（`n = 10⁵`、`m = 10⁴` 那组）	二分轮数
`max(Aᵢ)`（最紧）	99 995 341	42
`sum / m`	499 349 723	42
`1`（最松）	1	42

★ 三种下界，轮数一模一样 —— 因为决定轮数的是上界

二分的轮数是 ⌈log2(hi − lo + 1)⌉。这组数据里 hi = sum ≈ 5×10¹²，而三个下界分别是 1、5×10⁸、10⁸ —— 和 hi 比全都是零头，区间长度几乎没变，log2 自然也没变。

⇒ 「浪费几轮」实测是浪费 0 轮。⇒ 下界紧不紧，在这道题上完全不值得纠结 —— 值得纠结的只有「包没包住」。

★ 对照：暴力从 max 一个一个往上试要 432 632 690 次，二分 42 次。

6★★★ 两个各自无害的写法，凑在一起才错

回看第 ③ 步那张表最诡异的一列：

① NoBig（ok() 少一句 if (a[i] > limit) return false）：1500 轮，0 次出错
② Lo1（下界从 1 起）：只在「全是 0」时出错
④ 两个一起：157 / 283 / 324 —— 每档都错几百次

★★★ 为什么单独都没事

lo = max(Aᵢ) 保证了二分试到的每一个 mid 都 ≥ max(Aᵢ)，于是 if (a[i] > limit) return false 那一句永远轮不到执行 —— 删掉它当然不影响任何结果。

而 lo = 1 让二分真的会试到 mid < max(Aᵢ)，这时少了那句判断的 ok() 就会说谎：它把那个装不下的数单独切成一段就交差，可那一段的和仍然超过 limit。于是二分收敛到一个比真答案小的值。

⇒ lo = max(Aᵢ) 和 if (a[i] > limit) return false 是同一件事的两种写法。 留一个就够，两个都删就漏了。

⇒ 一般化：「这处改了没事」+「那处改了没事」≠「两处都改了没事」。 边界条件常常是成对出现的，而对拍只告诉你「这一版错没错」，不会告诉你「它是靠哪一处兜住的」。

7溢出：小数据 1500 轮一次都抓不到

p1182Int.cpp⑤ 全用 int

// ⚠ 只改一处：把 long long 换成 int
//
// 题面：N <= 10⁵、A_i < 10⁸ ⇒ **sum 最大 10¹³**，而 int 的上限是 2 147 483 647
//   —— 差了**四千多倍**，`hi = sum` 这一步直接溢出成负数，二分范围整个崩掉。
//
// ★ 但题面还有一句：「**答案不超过 10⁹**」—— 答案本身是装得进 int 的。
//   ⇒ 又一次「两笔溢出账，结论可以相反」（第 7 章 P1873 那条）：
//     **答案装得下，中间量装不下。** 溢出要一笔一笔算，不能只看输出那个数。
//
// ⚠ 小数据上它**一个字都不会错**（sum 才几百），只有满规模才现形 ——
//   见页面上那张表：三个档位的对拍全是 0，只有顶格数据抓得到。

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

static int n, m;
static vector<int> a;

static bool ok(int limit) {
    int seg = 1, cur = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] > limit) return false;
        if (cur + a[i] <= limit) cur += a[i];
        else { seg++; cur = a[i]; }
    }
    return seg <= m;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m)) return 0;
    a.assign(n, 0);
    int lo = 0, hi = 0;
    for (int i = 0; i < n; i++) { cin >> a[i]; lo = max(lo, a[i]); hi += a[i]; }   // ⚠ 这里溢出
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (ok(mid)) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

N ≤ 10⁵、Aᵢ < 10⁸ ⇒ sum 最大 10¹³，而 int 上限 2.1×10⁹ —— 差四千多倍。可小数据的 sum 才几百，离那条线差七八个数量级：

p1182GenBig.cpp顶格数据

// 顶格数据（P1182 计时 / 抓溢出用）：`./p1182GenBig <n> <m> <level>`
//
//   level 0  随机顶格：a_i ∈ [0, 10⁸)
//   level 1  ★ **把 sum 顶到最大**：a_i 全取 10⁸ − 1 ⇒ sum ≈ 10¹³
//            —— 这一档是专门冲着 int 溢出去的（见 p1182Int.cpp）：
//               小数据上 sum 才几百，`hi = sum` 那一步**根本溢不出来**。
//
// ⚠ 题面：N <= 10⁵、A_i < 10⁸、**答案 <= 10⁹**。
//   ★ 最后那条是题面**额外**给的保证，不是从 N、A_i 推出来的 ——
//     而它反过来卡住了 m 能取多小：a_i 都取 10⁸ − 1 时，一段最多装 **10** 个
//     （10 × 99999999 = 999999990 <= 10⁹），所以 **m 至少要 n/10**。
//   ⚠⚠ 第一版这里默认 m = 1000，造出来的答案是 9 999 999 900 ——
//     **顶格顶出了题面**（超了十倍），拿它量出来的东西不算数。
//     ⇒ 「顶格」是顶到题面的边上，不是顶到类型的边上。

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

int main(int argc, char** argv) {
    int n = (argc > 1) ? atoi(argv[1]) : 100000;
    int m = (argc > 2) ? atoi(argv[2]) : 10000;   // ⚠ 默认值要让答案落在 10⁹ 以内，见上
    int level = (argc > 3) ? atoi(argv[3]) : 0;
    mt19937 rng(20260827u);
    printf("%d %d\n", n, m);
    for (int i = 0; i < n; i++) {
        int v = (level == 1) ? 99999999 : (int)(rng() % 100000000u);
        printf("%d%c", v, i + 1 == n ? '\n' : ' ');
    }
    return 0;
}

点一下即可编辑

输出

点「运行 ▶」看结果

⇒ 三档 1500 轮，Int 版一次都没被抓到；只有顶格数据（n = 10⁵、Aᵢ 取到 10⁸）才让它和正解不一致。（第 6 章 P3406、第 7 章 P1873 那条的第三次： 溢出的触发条件是一条数值线，生成器够不够是算术题。）

⚠ 为什么这一页不写「它错成了多少」

hi += a[i] 在 int 上溢出是未定义行为。本机 g++ 15.2 从 -O0 到 -O3 再到 -fwrapv 都给同一个错值，但那是这台机器这个编译器的事，标准不保证。

⇒ 所以 check:viz 里钉的是「和正解不一致」这件事，不是那个具体的数。（本书踩过这个坑：UB 派生的数字换台机器就复现不出来。）

8一张总表

版本	只改了哪一处	对拍（1500 轮）	顶格	结果
`p1182`	——	——	8 毫秒	★ AC
① `p1182NoBig`	`ok()` 少一句	0	一致	侥幸对（被下界兜住）
② `p1182Lo1`	下界 `1`	8	一致	✗ 全 `0` 数据 WA
③ `p1182LoAvg`	下界 `sum/m`	0	一致	✓ 恒安全（鸽巢）
④ `p1182Both`	① ＋ ②	764	——	✗ WA
⑤ `p1182Int`	全用 `int`	0	不一致	✗ 满数据 WA

这一页记住三句话

★★★ 下界只要 ≤ 答案就安全，上界只要 ≥ 答案就安全。 出事的不是「松」也不是「紧」，是「没包住」—— lo = 1 出事是因为它 > 0，sum/m 没事是因为鸽巢原理保证了它 ≤ 答案。
★★★ 「这处改了没事」+「那处改了没事」≠「两处都改了没事」。 lo = max(Aᵢ) 和 ok() 里那句判断是同一件事的两种写法，删一个行，删俩就漏。
★★ 「放宽范围只是浪费几轮」实测是浪费 0 轮 —— 轮数由上界压倒性地决定。 ⇒ 别在下界紧不紧上花时间，只检查包没包住。

洛谷 P1182 数列分段 Section II

0题目原文（本地存了一份）

输入

输出

1⚠ 这一页不讲怎么做 —— 它是本章原题

2先把能 AC 的那一版摆在这儿

3四个「只改一处」的版本，命运完全不同

4★★★ 正文那个警告框里，有两句是错的

5★ 那「放宽范围要多花几轮」到底是几轮？—— 0 轮

6★★★ 两个各自无害的写法，凑在一起才错

7溢出：小数据 1500 轮一次都抓不到

8一张总表