Day 24 · 二分与数据结构综合

⏱今日时间安排

1二分 + 贪心：跳石头

先回忆一下昨天的第 2 节

看到「最短跳跃距离的最大值」这种问法，条件反射应该是：

三条全中，所以 P2678 就是一道标准的二分答案题。

check 的贪心怎么想

题目允许我们搬走至多 M 块石头，然后看所有「相邻落脚点」的距离里最小的那个能有多大。

现在假设我们已经定死了一个要求：所有跳跃距离都必须 ≥ x。那么从左往右走：

• 记住上一块留下来的石头位置 last（一开始是起点 0）。
• 看下一块石头 i。如果 a[i] - a[last] < x，说明从 last 跳到 i 太近了 —— 那就把 i 搬走，跳过它，last 不动。
• 如果距离够远，就踩上去，last = i。
• 扫完之后，看看一共搬走了几块。只要 ≤ M，就说明 x 能够做到。

★ 起点和终点怎么处理

题目说「不能移走起点和终点的岩石」，所以我们要另外对付终点 L。

做法很巧妙：把终点 L 也当成一块「石头」塞进数组末尾（下标 n+1），然后照常扫描。

扫描过程中如果终点离 last 也太近，代码一样会 cnt++。 这个 +1 的含义其实是：「连最后一块留着的石头也保不住，必须把它搬走」。

手算一遍样例

样例：L = 25，石头位置 2、11、14、17、21，最多搬走 M = 2 块。

所以 x = 4 做得到、x = 5 做不到 —— 答案就是 4，和洛谷样例一致。

题面提示也印证了：搬走 2 和 14 之后，最短距离是 4（17→21，或者 21→终点）。

2实数二分：银行贷款（今天的第一个新东西）

整数二分不够用了

昨天四道题的答案都是整数：高度、长度、段和、间距。 但 P1163 问的是月利率，答案是 2.9 这种小数。这时候二分还能用吗？能用， 而且更简单 —— 因为实数没有「相邻整数」的问题。

实数二分的循环怎么写？固定次数！

很多人会写 while(r - l > 1e-12)。这么写不算错，但有两个毛病：

• 精度 eps 不好定：写大了答案不精确，写小了可能因为浮点误差永远不收敛（死循环）。
• 迭代次数不确定，不好估计复杂度。

更稳的做法是：循环固定次数，比如 100 次。

for(int it = 0; it < 100; it++){     // 固定 100 次，绝不死循环
    double mid = (lo + hi) / 2;
    if(check(mid)) ...;
    else ...;
}

P1163 的 check 怎么想

题意：借了 w0 元，每月还 w 元，还 m 个月正好还清。求月利率。

给定一个月利率 r，我们可以模拟一遍还款过程：

double rem = w0;                    // rem = 现在还欠多少
for(int i = 0; i < m; i++){
    rem = rem * (1.0 + r) - w;      // 先按利率涨利息，再还掉 w
}
// 还完之后：rem > 0 表示还没还完；rem < 0 表示还多了

单调性很直观：利率越高，钱涨得越快，最后欠的就越多。 所以 rem 随 r 递增：r 太小 → rem 是负数（还多了），r 太大 → rem 是正数（还不完）。

我们要找的，就是让 rem ≈ 0 的那个 r。

防止数值爆炸：加一道保险

上界取 300%（即 r = 3）时，如果 m = 3000，那么中间过程会出现 1.05 × ... × 4³⁰⁰⁰ 这种 天文数字，直接变成 inf。虽然 inf 的正负号是对的（不会影响二分方向）， 但为了干净，我们在累乘过程中加一道「提前跳出」：

if(rem > 1e18){ rem = 1e18; break; }    // 已经爆炸，符号已确定，不用再算
if(rem < -1e18){ rem = -1e18; break; }

最后一步：按题目要求输出

题目要「月利率（用百分数表示），四舍五入精确到 0.1%」。所以最后要 × 100 再用 printf("%.1f") —— %.1f 自带四舍五入，正好符合要求。

3前缀和 + 同余：余数为 7

先复习前缀和（Day 15 学过）

前缀和数组 pre[i] = a[1] + a[2] + ... + a[i]，那么：

区间 [l, r] 的和 = pre[r] - pre[l-1];      // O(1) 求任意区间和

比起每次都重新累加（O(n)），前缀和把「求区间和」变成了 O(1)，这是拿空间换时间的老套路。

今天的新技巧：把「是 7 的倍数」翻译成「余数相等」

题目要求：找一段连续奶牛，使它们的 ID 之和是 7 的倍数，并且这段尽可能长。

如果暴力枚举左右端点，N = 50000 时要枚举 12.5 亿个区间，太慢。用前缀和就快多了：

于是问题变成了「找最远的同余点对」

余数只有 0~6 七种。对于每一种余数 r，我们只需要记住两件事：

• first[r]：余数 r 第一次出现在哪个下标；
• last[r]：余数 r 最后一次出现在哪个下标。

那么余数为 r 的最长区间长度就是 last[r] - first[r]（下标之差就是元素个数， 因为 pre[i] 和 pre[j] 之间的区间是 (i+1 .. j)，长度 = j - i）。

七种余数各算一遍，取最大，就是答案。整个算法 O(n)，7 个桶。

手算样例

样例：7 个数，分别是 3、5、1、6、2、14、10。

看余数 3：first = 1，last = 6，长度 = 6 - 1 = 5 ✅
看余数 1：first = 2，last = 4，长度 = 2；余数 0 只有下标 0，长度 0；余数 2 只有下标 3；余数 6 只有下标 7。
最大值是 5，正好是样例答案。

验证：下标 2~6 对应的数是 5、1、6、2、14，和 = 28 = 7 × 4 ✅（题面提示里也是这个例子）。

4最大子段和：Kadane 算法（线性 DP 的第一课）

题目很简单：找一段连续的子数组，让和最大

数列 2 -4 3 -1 2 -4 3，选一段连续的，让和最大。 选 3 -1 2 和为 4 —— 这就是样例答案。

从暴力到 O(n)，一步步来

n 最大 2×10⁵，O(n²) 是 4×10¹⁰ 次运算，肯定超时。必须用 O(n)。

核心思想：以 i 结尾的最大子段和

定义 f[i] = 「以第 i 个数结尾」的所有子段里，和最大的那个。

那 f[i] 只有两种来源：

• 接在前面：f[i-1] + a[i]；
• 从自己重新开始：a[i]（前面的统统不要）。

走一遍样例

看第 3 步：f[2] = -2 是负数，所以 f[3] 果断选择「从 3 重新开始」而不是「-2 + 3 = 1」。 这就是 Kadane 的灵魂。最后答案是 4。

拓展：二维怎么套这个模板

计划里还提了一句「二维前缀和 + 枚举：把二维压成一维再求最大子段和」。 这就是经典的「最大加权矩形」问题（Day 15 的 P1719），思路非常漂亮：

• 枚举矩形的上边界 top 和下边界 bottom（两层循环）。
• 把 top 到 bottom 之间，每一列的元素加起来，压成一个一维数组 col[]。
• 对这个 col[] 求最大子段和—— 找到的那一段就对应矩形的左右边界。

下面这段拓展代码我用洛谷 P1719 的官方样例实测过：

4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

15

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int a[125][125];
int col[125];        // col[j] = 当前上下边界之间，第 j 列的元素和

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> a[i][j];

    long long best = -1000000000LL;   // ★ 答案可能是负数，不能初始化成 0

    // 枚举上边界 top 和下边界 bottom，把这两行之间的每一列压缩成一个数
    for(int top = 1; top <= n; top++){
        for(int j = 1; j <= n; j++) col[j] = 0;
        for(int bottom = top; bottom <= n; bottom++){
            for(int j = 1; j <= n; j++) col[j] += a[bottom][j];
            // 现在问题变成了「一维数组 col[1..n] 的最大子段和」，直接 Kadane
            long long cur = col[1], mx = col[1];
            for(int j = 2; j <= n; j++){
                cur = max((long long)col[j], cur + col[j]);
                mx = max(mx, cur);
            }
            best = max(best, mx);
        }
    }
    cout << best << endl;
    return 0;
}

这个「降维」思路能解决一大类二维区间问题。更重要的是 —— 你已经写出了人生第一个「非平凡」DP 的转移方程 cur = max(col[j], cur + col[j])。 明天 Day 25 的线性 DP，就是把这个思路正式系统化。

5四道例题详解

同样地，下面四段代码都用 g++（-std=c++14 -O2 -Wall）实际编译过，并用洛谷官方样例跑过。

25 5 2
2
11
14
17
21

4

#include <iostream>
using namespace std;

int L, n, m;
int a[50005];                // a[0]=起点0, a[1..n]=中间石头, a[n+1]=终点L

// check(x)：能不能通过搬走 <= m 块石头，让所有「相邻落脚点」的距离都 >= x
bool check(int x){
    int cnt = 0;             // 搬走的石头数
    int last = 0;            // 上一块留下来的石头（下标），0 号是起点
    for(int i = 1; i <= n + 1; i++){
        if(a[i] - a[last] < x){   // 从 last 跳到 i 太近了 -> 把 i 搬走
            cnt++;
        } else {
            last = i;             // 距离够远，这块踩上去
        }
    }
    return cnt <= m;         // 搬走的不超过 m 块，x 就可行
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> L >> n >> m;
    a[0] = 0;
    for(int i = 1; i <= n; i++) cin >> a[i];
    a[n + 1] = L;            // ★ 终点当成最后一块「石头」参与判断

    // 要求「最短跳跃距离的最大值」：x 越大越难做到 -> 单调
    int l = 1, r = L, ans = 0;
    while(l <= r){                      // 模板 A：ans 记录 + 区间跨越 mid
        int mid = l + (r - l) / 2;
        if(check(mid)){                 // mid 能做到，记下来，再贪心地试试更大
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;                // 做不到，只能往小找
        }
    }
    cout << ans << endl;
    return 0;
}

1000 100 12

2.9

#include <iostream>
using namespace std;

int main(){
    double w0, w;            // w0 = 贷款原值, w = 每月还款额
    int m;                   // m = 还款月数
    cin >> w0 >> w >> m;

    // 二分月利率 r：r 越大，还完 m 个月后剩下的欠款越多 -> 单调
    // 题目保证答案不超过 300%，所以利率（小数形式）一定在 [0, 3] 内
    double lo = 0.0, hi = 3.0;
    for(int it = 0; it < 100; it++){      // 固定迭代 100 次，比 while(hi-lo>eps) 更稳
        double mid = (lo + hi) / 2;
        double rem = w0;                  // rem = 当前还欠银行多少
        for(int i = 0; i < m; i++){
            rem = rem * (1.0 + mid) - w;  // 每月先算利息，再还掉 w
            if(rem > 1e18){ rem = 1e18; break; }    // 数值已经爆炸，符号已确定，直接收工
            if(rem < -1e18){ rem = -1e18; break; }
        }
        if(rem < 0) lo = mid;             // 最后还多了 -> 利率太低，要调高
        else hi = mid;                    // 最后还欠着 -> 利率太高，要调低
    }
    // 换成百分数，四舍五入到 0.1%
    printf("%.1f\n", (lo + hi) / 2 * 100);
    return 0;
}

7
3
5
1
6
2
14
10

5

#include <iostream>
#include <cstdio>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);

    int first[7], last[7];               // 每个余数第一次/最后一次出现的前缀下标
    for(int r = 0; r < 7; r++){ first[r] = -1; last[r] = -1; }

    int pre = 0;                         // 前缀和 mod 7，即 sum[0] = 0
    first[0] = 0;  last[0] = 0;          // ★ 余数 0 在下标 0 就出现过，别忘了

    for(int i = 1; i <= n; i++){
        int x;
        scanf("%d", &x);
        pre = (pre + x % 7) % 7;         // 边读边取模，永远不会溢出
        if(first[pre] == -1) first[pre] = i;
        last[pre] = i;
    }

    // 若 sum[r] ≡ sum[l-1] (mod 7)，则区间 (l..r) 的和是 7 的倍数
    // 长度 = r - (l-1)，所以每个余数都取「最后一次出现 - 第一次出现」
    int ans = 0;
    for(int r = 0; r < 7; r++){
        if(first[r] != -1 && last[r] - first[r] > ans)
            ans = last[r] - first[r];
    }
    printf("%d\n", ans);
    return 0;
}

f[i] = max(a[i], f[i-1] + a[i]);       // 要么接上前面，要么从自己重新开始

7
2 -4 3 -1 2 -4 3

4

#include <iostream>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;

    long long best = 0, cur = 0;   // best=全局最优, cur=以当前数结尾的最大子段和
    for(int i = 1; i <= n; i++){
        long long x;
        cin >> x;
        if(i == 1){
            best = cur = x;        // ★ 第一个数直接作为初始状态（不能初始化成 0）
            continue;
        }
        // f[i] = max(a[i], f[i-1] + a[i])
        // 前面的累加和如果是负的，还不如从 x 重新开始
        cur = (cur + x > x) ? (cur + x) : x;
        if(cur > best) best = cur;
    }
    cout << best << endl;
    return 0;
}

6今日常见错误汇总

✓自测：你真的会了吗

for(int top = 1; top <= n; top++){
    memset(col, 0, sizeof(col));              // 清空列和
    for(int bottom = top; bottom <= n; bottom++){
        for(int j = 1; j <= n; j++) col[j] += a[bottom][j];  // 累加列和
        // 在这里对 col[] 跑一次 Kadane
    }
}

▤速查卡（截图存手机）

【二分 + 贪心（P2678 型：最大化最小值）】
  把起点 0 和终点 L 一起放进数组
  check(x):
      cnt = 0; last = 0(起点下标);
      for i = 1 .. n+1:
          if(a[i] - a[last] < x) cnt++;     // 太近，搬走当前
          else last = i;                    // 够远，踩上去
      return cnt <= M;
  用昨天模板 A：可行 → ans = mid, l = mid + 1

【实数二分（P1163 型）】
  double lo = 下界, hi = 上界;      // 有解区间，别乱开
  for(int it = 0; it < 100; it++){  // ★ 固定次数，不死循环
      double mid = (lo + hi) / 2;
      if(check(mid)) hi = mid;      // 或 lo = mid，看单调方向
      else           lo = mid;
  }
  printf("%.1f\n", (lo + hi) / 2 * 100);   // %.1f 自带四舍五入
  // 中间量可能爆 double 时，加 if(rem > 1e18){ rem = 1e18; break; }

【前缀和 + 同余（P3131 型）】
  // 区间和能被 k 整除  ⟺  两个前缀和 mod k 相等
  int first[7], last[7];            // 全初始化为 -1
  int pre = 0;
  first[0] = last[0] = 0;           // ★ pre[0] = 0 要先登记
  for(i = 1..n){
      cin >> x;
      pre = (pre + x % 7) % 7;      // 边读边取模，不溢出
      if(first[pre] == -1) first[pre] = i;
      last[pre] = i;
  }
  ans = max(last[r] - first[r]);    // 长度就是下标差，别 +1

【最大子段和 Kadane（P1115）】
  long long cur = a[1], best = a[1];      // ★ 不能用 0 初始化！
  for(i = 2..n){
      cur = max(a[i], cur + a[i]);        // f[i] = max(a[i], f[i-1]+a[i])
      best = max(best, cur);
  }
  // 子段必须非空 → 全负数时输出最大的那个负数

【二维压一维（最大加权矩形）】
  for top = 1..n:
      col[] 清零
      for bottom = top..n:
          col[j] += a[bottom][j]   // 累加列和
          对 col[] 跑一次 Kadane
  // 复杂度 O(n^3)

→明天预告 · Day 25

动态规划入门：线性 DP

今天你已经偷偷用过一次 DP 了 —— 最大子段和的 cur = max(a[i], cur + a[i]) 就是一个正儿八经的状态转移方程。 明天我们要把这个「凭感觉写出来」的东西，变成有章法可循的套路。

明天会见到的四道题：

• P1216 数字三角形：DP 的「Hello World」，从金字塔顶走到底，路上数字和最大。
• P1002 过河卒：棋盘上的路径计数，顺便复习二维数组。
• P1091 合唱队形：正着求一遍最长上升子序列，倒着再求一遍。
• P1990 覆盖墙壁：用 2×1 骨牌和 L 型砖铺满 2×N 的墙，按「第一块砖怎么放」分类讨论递推。

每道题都按四要素来分析：① 状态定义 ② 转移方程 ③ 初始化 ④ 答案在哪。 今天先把这个口诀记住，明天逐题套。

另外，明天开始务必养成习惯：写完 DP 先手推样例表格， 就像今天最大子段和那张表一样 —— 表算对了，代码基本不会错。