20 · 回顾四：贪心与前缀和

贪心策略：排序后让最贵的 p[r] 先决定命运——若能配上最便宜的 p[l]（p[l] + p[r] ≤ w），就配成一组；否则 p[r] 单独一组。

交换论证：设最优解里 p[r] 与 x 配对。若 x 不是最便宜的 p[l]，因为 p[l] ≤ x，把 x 换成 p[l]，和不会超限、组数不变。若最优解里 p[r] 单独一组，而 p[l] 与 y 配对，把这两组合并成 (p[r], p[l]) 和 (y) ，组数同样不变。所以“能配就配最便宜的”一定存在最优解。

双指针实现：l 从左、r 从右。每轮至少出局一件（配成一组出局两件），共 O(n) 轮；总复杂度是排序的 O(n log n)。

只剩一件（l == r）时不能自己配自己，直接单独一组，这也是最容易漏的边界。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int w, n;
    cin >> w >> n;
    vector<int> p(n);
    for (int i = 0; i < n; ++i) cin >> p[i];
    sort(p.begin(), p.end());          // 排序后两端才是“最便宜 / 最贵”

    int l = 0, r = n - 1, cnt = 0;
    while (l <= r) {
        if (l == r) { ++cnt; break; }               // 只剩一件：单独一组
        if (p[l] + p[r] <= w) { ++l; --r; }         // 能配就配，两件一起出局
        else { --r; }                              // 配不上，最贵的单独一组
        ++cnt;
    }

    cout << cnt << "\n";
    return 0;
}

贪心策略：按单价 v_i / m_i 从大到小排序，依次尽量取满；遇到装不下的那一种，只取剩余容量的那一份，然后结束。

交换论证：设最优解里取了一部分单价较低的物品 B，而单价较高的物品 A 没有取完。把 B 的一份重量换成 A 的一份重量：总重量不变，总价值不减。所以一定存在一个“按单价降序取满”的最优解。

为什么这题能贪、0/1 背包不能：物品可以切开，“取多少”是连续的，交换时总能换出任意小的量；0/1 背包只能整件拿，交换会破坏可行性。这正好落在第 16 节那张判据表的“是否消耗未来资源”上。

实现要点：排序比较用交叉相乘 a.v * b.m > b.v * a.m，不写除法；答案用 double，最后一种物品按重量比例折算。

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

struct Item { int m, v; };

bool cmp(const Item &a, const Item &b) {
    // 单价降序：a.v/a.m > b.v/b.m，交叉相乘，避开浮点误差
    return 1LL * a.v * b.m > 1LL * b.v * a.m;
}

int main() {
    int n, t;
    cin >> n >> t;
    vector<Item> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i].m >> a[i].v;
    sort(a.begin(), a.end(), cmp);

    double ans = 0;
    for (int i = 0; i < n; ++i) {
        if (t >= a[i].m) {                  // 装得下就整件拿
            t -= a[i].m;
            ans += a[i].v;
        } else {                            // 只能拿剩余容量的那一份
            ans += 1.0 * a[i].v * t / a[i].m;
            t = 0;
            break;                          // 背包已满，后面的单价更低，不用再看
        }
    }

    printf("%.2f\n", ans);
    return 0;
}

反向思考：锯一次，一块长 S 的木板的代价是 S，得到长 a、b 的两块，且 S = a + b；倒过来看，就是“把 a、b 两块并成 S，代价 S = a + b”。两种过程的总代价一一对应。

于是问题等价于：每次合并最短的两段，直到只剩一段，求最小总代价——这就是哈夫曼（合并果子）。第 17 节已经证过：若某次合并的不是最短的两段，换成最短的两段，本次代价变小，而且新段更短，对后续只会更有利。

复杂度：n − 1 次合并，每次两次 pop 一次 push，O(n log n)；n = 2×10⁴ 时不到 3×10⁵ 次堆操作。

量级：每段 5×10⁴、n = 2×10⁴ 时累计代价可达 10¹⁰ 量级，堆和答案都用 long long。

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

int main() {
    int n;
    cin >> n;

    // 小根堆：每次都要取最短的两段
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    for (int i = 0; i < n; ++i) {
        long long x;
        cin >> x;
        pq.push(x);
    }

    long long ans = 0;
    while (pq.size() >= 2) {
        long long a = pq.top(); pq.pop();   // 最短的一段
        long long b = pq.top(); pq.pop();   // 次短的一段
        ans += a + b;                       // 合并代价 = 拼接后的长度
        pq.push(a + b);                     // 新段放回去，继续参与合并
    }

    cout << ans << "\n";
    return 0;
}

换个说法（差分）：令 d_0 = 0，答案 = Σ max(0, d_i − d_{i−1})，即所有上升量之和。

下界：每次操作只让“某一段连续区间”各减 1，因此一个上升沿有多高，就至少需要那么多次操作去削平它；把所有上升沿加起来，就是任何方案都逃不掉的下界。

可达：从左往右扫，遇到 d_i > d_{i−1} 就新开 d_i − d_{i−1} 次操作，并让这些操作与前面仍有“余量”的操作并行推进——每个位置都能恰好被削到 0。下界可达，即答案。

实现：连数组都不用开：读一个数与上一个比较，只累加上升量，O(n) 时间、O(1) 空间。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    long long ans = 0;   // 答案上限 10^5 × 10^4 = 10^9，long long 更稳
    int prev = 0;        // 相当于 d[0] = 0

    for (int i = 1; i <= n; ++i) {
        int d;
        cin >> d;
        if (d > prev) ans += d - prev;   // 只累加“上升”的部分
        prev = d;
    }

    cout << ans << "\n";
    return 0;
}

双指针：维护窗口 [l, r] 的整数和 sum，初始 l = 1、r = 2、sum = 1 + 2 = 3。

sum < M：右端右移一格，sum 加上新的 r。sum > M：左端右移一格，sum 减去旧的 l。sum == M：输出 l、r，再把左端右移，继续找下一段。

为什么 O(M)：l 与 r 都只增不减，各自最多走到 M，总移动次数 O(M)；M = 2×10⁶ 时不到 10⁷ 次加减，几十毫秒就完。

为什么不会漏：固定 l 时 sum 随 r 严格递增，一旦 sum ≥ M 就没有更长的段适合这个 l，只能右移 l——这就是“窗口单调”的全部依据。

边界：循环写 while (l < r)。l == r 时窗口只剩一个数，题目不允许；而且此时任何以 l 开头的更长的段之和都已超过 M。

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

int main() {
    int M;
    cin >> M;

    int l = 1, r = 2;
    long long sum = 3;              // 当前窗口 [l, r] 内所有数之和

    while (l < r) {                 // l == r 表示只剩一个数，题目要求至少两个数
        if (sum == M) {
            cout << l << " " << r << "\n";
            sum -= l;
            ++l;                    // 这一段找完，左端右移继续找下一段
        } else if (sum < M) {
            ++r;                    // 先让 r 前进
            sum += r;               // 再把新的 r 纳入窗口
        } else {
            sum -= l;               // 和太大，把左端移出窗口
            ++l;
        }
    }

    return 0;
}