📖 第 4.3 章 ⏱️ 约 55 分钟 🥈 Silver

第 4.3 章：排序、匹配与构造

这一章的贪心都有一个共同形态：给元素找到一个「正确的顺序」——自定义比较器、双序列同向配对、或一遍扫描构造答案。USACO 里「按某种顺序排列 N 个东西」的题几乎都在这里。

📌 前置： 第 4.1 章的交换论证法（证明「正确顺序」为什么正确）。

4.3.1 排列贪心：自定义排序标准

顺序	A 的完成时间	B 的完成时间	两者之和
A → B	T + a	T + a + b	2T + 2a + b
B → A	T + b	T + b + a	2T + a + 2b

经典题二：最大数（拼接贪心）

题目： 给定 N 个非负整数，将它们排列后拼接成最大的数。输出为字符串。

样例输入：

5
3 30 34 5 9

样例输出：

（排序比较规则：a+b > b+a。注意 3 应排在 30 前面，因为 "330" > "303"）

数据规模： 1 ≤ N ≤ 10⁵；每个数 ≤ 10⁹（作为字符串读入更方便）；结果可能非常长（上百万位），必须按字符串处理。

贪心策略： 自定义比较器：对两个数 a 和 b（作为字符串），若 str(a) + str(b) > str(b) + str(a) 则 a 排在 b 前面。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<string> nums(n);
    for (string &s : nums) cin >> s;

    // 自定义排序：a+b > b+a 时 a 排在前面
    sort(nums.begin(), nums.end(), [](const string &a, const string &b) {
        return a + b > b + a;
    });

    // 边界情况：全为零
    if (nums[0] == "0") {
        cout << "0\n";
        return 0;
    }

    string result = "";
    for (const string &s : nums) result += s;
    cout << result << "\n";
    return 0;
}
// 时间复杂度：O(N log N · L)，L = 最大数字位数

Largest Number by Custom Comparator

逐步追踪（nums = ["3", "30", "34", "5", "9"]）：

比较部分对：
"3"+"30"="330" vs "30"+"3"="303"  →  "3" 排前面
"9"+"5"="95"  vs "5"+"9"="59"    →  "9" 排前面
"34"+"3"="343" vs "3"+"34"="334" →  "34" 排前面

排序后：["9", "5", "34", "3", "30"]
结果：  "9534330" ✓

⚠️ 警告： 不能简单地按数值大小排序！例如 "3" > "30" 按数值，但拼接 "330" > "303"，所以 "3" 应排前面。始终用拼接比较器。

经典题四（USACO Bronze）：最小代价排序（相邻交换）

题目： N（1 ≤ N ≤ 10⁵）头奶牛站成一排，奶牛 i 的「暴躁值」为 g[i]（1 ≤ g[i] ≤ 10⁹，两两互不相同）。想排序这一排使暴躁值严格递增。唯一允许的操作是交换两头相邻的奶牛。交换第 i 和 j 位置的奶牛（相邻）时，代价为 g[i] + g[j]。求排序所需的最小总代价。答案可能超过 int 范围，用 64 位整数。

输入格式： 第一行 N；第二行 N 个整数 g₁, …, g_N。 数据规模： 1 ≤ N ≤ 10⁵，1 ≤ g[i] ≤ 10⁹。下方 O(N²) 逆序对暴力用于理解；正式提交需改为归并排序数逆序对（O(N log N)）。

样例输入：

3
3 1 2

样例输出：

逆序对方案（O(N²)）：

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<long long> g(n);
    for (long long &x : g) cin >> x;

    // 总代价 = 每对逆序对 (i,j)（i<j，g[i]>g[j]）的 g[i]+g[j] 之和
    long long totalCost = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (g[i] > g[j]) {
                totalCost += g[i] + g[j];  // 这个逆序对的代价
            }
        }
    }

    cout << totalCost << "\n";
    return 0;
}
// 时间：O(N²) — N ≤ 10^5 时用归并排序逆序对计数（O(N log N)）

验证： 对 [3,1,2] 的冒泡排序：

交换(3,1) = 代价 4 → [1,3,2]
交换(3,2) = 代价 5 → [1,2,3]
总计 = 9 ✓

4.3.2 任务分配：双序列匹配

任务分配问题涉及将两个有序序列的元素匹配以优化某个目标。关键模式：对两个序列排序，然后用双指针扫描或直接下标配对。

经典题（USACO Silver）：配对——排列不等式实战

题目： 你有 A 组 N 头奶牛和 B 组 N 头奶牛（1 ≤ N ≤ 10⁵）。必须将 A 中每头奶牛与 B 中恰好一头配对（一对一）。奶牛 a 与奶牛 b 配对的利润是 min(a, b)，其中 1 ≤ a, b ≤ 10⁹。最大化 N 对的总利润。总利润可能超过 int 范围。

输入格式： 第一行 N；第二行 A 组的 N 个整数；第三行 B 组的 N 个整数。 数据规模： 1 ≤ N ≤ 10⁵，1 ≤ a[i], b[i] ≤ 10⁹。排序 O(N log N) 轻松通过。

样例输入：

3
1 3 5
2 4 6

样例输出：

追踪（两数组升序排序后按下标配对）：

A 排序后：[1, 3, 5]
B 排序后：[2, 4, 6]

配对 (1,2)：min=1
配对 (3,4)：min=3
配对 (5,6)：min=5
总计 = 1+3+5 = 9 ✓

为什么同向排序？ 交换论证：若某个配对中 a₁ < a₂ 与 b₁ > b₂ 配对（A 升序但 B 不是），交换到同向配对总是不差的（见 4.3.1 节排列不等式）。

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

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

    vector<int> A(n), B(n);
    for (int &x : A) cin >> x;
    for (int &x : B) cin >> x;

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    long long total = 0;
    for (int i = 0; i < n; i++) {
        total += min(A[i], B[i]);  // 第 i 小的与第 i 小的配对
    }

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

贪心模拟（USACO Bronze）：奶牛信号

许多 USACO Bronze 题是带贪心技巧的纯模拟：按时间顺序处理事件，在每步贪心维护最优状态。关键是确定模拟什么以及按什么顺序。

题目： N（1 ≤ N ≤ 10⁵）头奶牛各想从牛棚出发到达牧场。奶牛 i 准备在时间 t[i]（0 ≤ t[i] ≤ 10⁹）离开。牛棚和牧场之间的路同时最多容纳 C（1 ≤ C ≤ N）头奶牛，过路恰好需要 1 个时间单位。路满时奶牛在牛棚等待。假设尽早送奶牛出发，最后一头奶牛何时到达？

输入格式： 第一行 N 和 C；第二行 N 个整数 t₁, …, t_N。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, c;
    cin >> n >> c;

    vector<int> t(n);
    for (int &x : t) cin >> x;
    sort(t.begin(), t.end());  // 按出发时间顺序处理

    int ans = 0;
    // 每 c 头奶牛一组处理
    for (int i = 0; i < n; i += c) {
        // 这批奶牛中最早的是 t[i]
        ans = max(ans, t[i]);  // 这批出发时间至少要等最早的奶牛准备好
        ans++;  // 过路需要 1 个时间单位
    }

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

4.3.3 区间合并

区间合并是另一种经典贪心：将所有重叠区间合并为一组不重叠的区间。

题目： 给定 N 个区间 [l[i], r[i]]，把相互重叠（或共享端点）的区间合并，输出合并后的区间列表。（1 ≤ N ≤ 10⁵，−10⁹ ≤ l[i] ≤ r[i] ≤ 10⁹。）

样例输入：

样例输出：

1 个合并区间：
[0,10]

（5 个区间首尾相连，全部重叠，合并为一个 [0,10]）

样例输入二：

样例输出二：

3 个合并区间：
[1,6] [8,10] [15,18]

（[1,3] 与 [2,6] 重叠合并；[8,10] 与 [15,18] 与前后均不相连）

贪心算法：

按左端点升序排序区间
维护当前合并区间 [curL, curR]
对每个新区间 [l, r]：
- 若 l ≤ curR（重叠或相邻）：延伸 curR = max(curR, r)
- 否则：完成当前合并区间，开始新的

Interval Merging — Step-by-Step

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<pair<int,int>> intervals(n);
    for (auto &[l, r] : intervals) cin >> l >> r;

    sort(intervals.begin(), intervals.end());  // 按左端点排序

    vector<pair<int,int>> merged;

    for (auto [l, r] : intervals) {
        if (merged.empty() || l > merged.back().second) {
            // 无重叠——开始新的合并区间
            merged.push_back({l, r});
        } else {
            // 重叠——延伸右端点
            merged.back().second = max(merged.back().second, r);
        }
    }

    cout << merged.size() << " 个合并区间：\n";
    for (auto [l, r] : merged) {
        cout << "[" << l << "," << r << "] ";
    }
    cout << "\n";
    return 0;
}
// 时间复杂度：O(N log N)

逐步追踪（输入已排序：[1,3],[2,6],[8,10],[15,18]）：

[1,3]:   merged 为空 → 直接加入。merged=[[1,3]]
[2,6]:   2 <= 3（重叠）→ 延伸：[1, max(3,6)]=[1,6]。merged=[[1,6]]
[8,10]:  8 > 6（不重叠）→ 加新区间。merged=[[1,6],[8,10]]
[15,18]: 15 > 10（不重叠）→ 加新区间。merged=[[1,6],[8,10],[15,18]]

输出：[[1,6],[8,10],[15,18]] ✓

4.3.4 字典序构造贪心

「构造字典序最小/最大的序列」是一大类贪心题的统称。核心思路一致：序列前面的位置影响最大，所以贪心地让越靠前的位置越优——每一步在「合法的候选」里选使前缀最优的那个，用一个可增删的候选集合维护后面的选择空间。

本节的三个经典题全是这个模式的不同外衣：删数字 = 每步保留让前缀最小的数字；跳跃/股票 = 从左到右每步取局部最优。

经典题：删除 K 个数字得到最小数（字典序最小构造）

题目： 给定一串数字（表示一个大整数），恰好删除 K 个数字（保持剩余数字的原始顺序）以形成最小的整数。

数据规模： 数字串长度 L ≤ 10⁶，1 ≤ K < L；结果可能带前导零，需去除。O(N) 单调栈是唯一可行做法。

例子：

"1432219"，K=3  →  "1219"

贪心思路： 维护单调栈。从左到右扫描：

若栈顶 > 当前数字且还有删除机会：弹出栈顶（删除较大的数字）
否则：压入当前数字
扫描完后若还有删除机会：从栈的右端删除

Monotone Stack — Remove K Digits

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

int main() {
    string num;
    int k;
    cin >> num >> k;

    string stk = "";  // 用字符串作单调栈

    for (char c : num) {
        // 当栈顶大于当前数字且还有删除机会时弹出
        while (k > 0 && !stk.empty() && stk.back() > c) {
            stk.pop_back();
            k--;
        }
        stk.push_back(c);
    }

    // 若还有删除机会，从右端删除
    stk.resize(stk.size() - k);

    // 移除前导零
    int start = 0;
    while (start < (int)stk.size() - 1 && stk[start] == '0') start++;

    cout << stk.substr(start) << "\n";
    return 0;
}
// 时间复杂度：O(N)

经典题：买卖股票最大利润（贪心版）

题目： 给定每日股价，可以无限次买卖（但每次只能持有一股），最大化总利润。

样例输入：

6
7 1 5 3 6 4

样例输出：

（捕获所有上涨段：(5−1) + (6−3) = 4 + 3 = 7）

数据规模： 1 ≤ N ≤ 10⁵，1 ≤ price[i] ≤ 10⁹。N = 10⁵ 时逐日 O(N) 贪心即可，无需更复杂方法。

贪心思路： 只要明天价格高于今天，就「今天买明天卖」。等价于累加所有正日差。

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

int main() {
    int n;
    cin >> n;
    vector<int> prices(n);
    for (int &x : prices) cin >> x;

    int profit = 0;
    for (int i = 1; i < n; i++) {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];  // 捕获每次上涨
        }
    }

    cout << profit << "\n";
    return 0;
}
// 时间复杂度：O(N)

Stock Trading — Capture Every Rise

⚠️ 注意： 这是「无限次交易」版本。「最多一次交易」→ 追踪最低买入价的单次扫描。「最多两次/K 次交易」→ 需要 DP。

转化（关键一步）： 设平均值 avg。令 S[i] = (a[1]−avg) + … + (a[i]−avg)——「前 i 堆净多出的牌数」。第 i 堆与第 i+1 堆之间的移动量至少是 |S[i]|（前 i 堆多余的牌必须穿过这条边界流向右边，不足则从右边流入）。总移动次数 = Σ|S[i]|——又变成了「仓库选址」！让所有 S[i] 靠近某个值 t，最优 t 就是 S[1..N−1] 的中位数。

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

int main() {
    int n; cin >> n;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;
    long long total = 0;
    for (long long x : a) total += x;
    long long avg = total / n;             // 题目保证整除

    vector<long long> S(n + 1, 0);
    for (int i = 1; i <= n; i++) S[i] = S[i-1] + a[i-1] - avg;

    sort(S.begin(), S.end());
    long long med = S[n / 2];
    long long ans = 0;
    for (int i = 0; i <= n; i++) ans += llabs(S[i] - med);
    cout << ans << "\n";
}

（样例：avg=10，S = [0, −1, −2, 5, −1]，中位数 −1，Σ|S[i]−(−1)| = 1+0+1+6+0 = 8。）

💡 环形版本（进阶）： 若堆围成一圈，「断开位置」有 N 种选法——对每个断点算一次上述答案，取最小。经典优化是把断点的贡献排序后一次扫描求出，总复杂度 O(N log N)。这题在 USACO 风格的「Circular Barn」系列中反复出现。

中位数贪心的识别信号： 题目要「最小化 |距离/差| 的总和」或「均分」，且每个量的移动/调整是独立的——找中位数，不是平均数。

练习题

题目	关键技术	难度
4.3.1 统计干草堆（USACO Bronze）	排序 + 二分统计	🟢 简单
4.3.2 睡觉奶牛排序（USACO Bronze）	有序后缀观察	🟢 简单
4.3.3 任务调度器	频率公式贪心	🟡 中等

题目 4.3.1 — USACO 2016 December Bronze：统计干草堆

题目： N 捆干草放在数轴上（位置可重复）。Q 次查询：范围 [L, R] 内有多少捆干草？

输入格式： 第一行 N 和 Q；第二行 N 个整数位置；接下来 Q 行每行两个整数 L 和 R。 数据规模： 1 ≤ N, Q ≤ 10⁵，0 ≤ 位置 ≤ 10⁹，0 ≤ L ≤ R ≤ 10⁹。每次查询 O(log N) 的二分才能通过；O(N) 扫描每次查询会超时。

示例：

N=7, Q=4
位置：6 3 2 7 5 1 4
查询：2 5 / 1 1 / 4 8 / 10 15

输出：

💡 提示

排序位置，然后用 lower_bound / upper_bound 二分搜索统计 [L, R] 内的元素。这道题练习「排序 + 二分搜索」思维——大多数贪心算法的第一步。

排序后，[L, R] 内的数量 = upper_bound(R) - lower_bound(L)。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    vector<int> pos(n);
    for (int &x : pos) cin >> x;
    sort(pos.begin(), pos.end());  // 关键：先排序以支持二分搜索

    while (q--) {
        int l, r;
        cin >> l >> r;

        auto lo = lower_bound(pos.begin(), pos.end(), l);
        auto hi = upper_bound(pos.begin(), pos.end(), r);

        cout << (hi - lo) << "\n";
    }

    return 0;
}
// 时间复杂度：O(N log N + Q log N)

题目 4.3.2 — USACO 2019 February Bronze：睡觉奶牛排序

题目： N（1 ≤ N ≤ 10⁵）头奶牛编号 1~N 以随机顺序站成一排。每次操作：取出排尾的奶牛，将其插入任意位置。最少几次操作能让队伍变为 1, 2, ..., N 的顺序？

输入格式： 第一行 N；第二行 N 个整数表示队伍从头到尾的编号。 数据规模： 1 ≤ N ≤ 10⁵。O(N) 扫描即可。

示例：

N=5
顺序：1 4 2 5 3

输出：4

💡 提示

核心思路： 找队尾已经有序的最长后缀（连续的 k, k+1, ..., N）。这些奶牛不需要移动。答案 = N − 后缀长度。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> cows(n);
    for (int &x : cows) cin >> x;

    // 找最长已排序后缀：cows[i], cows[i+1], ..., cows[n-1]
    // 条件：cows[i] + 1 == cows[i+1]（连续递增）
    int keep = 1;  // 至少最后一头奶牛留下
    for (int i = n - 2; i >= 0; i--) {
        if (cows[i] + 1 == cows[i + 1]) {
            keep++;
        } else {
            break;  // 后缀必须连续——遇到第一个断点就停
        }
    }

    cout << n - keep << "\n";
    return 0;
}
// 时间复杂度：O(N)

题目 4.3.3 — 任务调度器 🟡 中等

题目： N 个标有 A~Z 的任务（1 ≤ N ≤ 10⁴，任务标号仅大写字母），每个需要 1 个时间单位。执行标有 X 的任务后，CPU 必须等待至少 k（0 ≤ k ≤ 100）个时间单位才能再次执行 X（期间可运行其他任务或空闲）。找完成所有任务的最短总时间。

输入格式： 第一行 N 和 k；第二行 N 个用空格分隔的大写字母。

示例：

tasks = [A, A, A, B, B, B], k = 2

输出：8（A→B→空闲→A→B→空闲→A→B）

💡 提示

关键公式：ans = max(任务总数, (maxCount-1)*(k+1) + countMax)

其中 maxCount = 出现次数最多的任务的频率。

贪心策略：每个「帧」（每 k+1 个时间单位）先填最频繁的剩余任务。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    vector<int> freq(26, 0);
    for (int i = 0; i < n; i++) {
        char c; cin >> c;
        freq[c - 'A']++;
    }

    int maxCount = *max_element(freq.begin(), freq.end());
    int countMax = count(freq.begin(), freq.end(), maxCount);

    int ans = max(n, (maxCount - 1) * (k + 1) + countMax);

    cout << ans << "\n";
    return 0;
}
// 时间复杂度：O(N)

C++ 竞赛编程：USACO 学习指南

第 4.3 章：排序、匹配与构造

4.3.1 排列贪心：自定义排序标准

经典题一：最小化总完成时间（最短作业优先）

经典题二：最大数（拼接贪心）

经典题三：最大化（或最小化）内积

经典题四（USACO Bronze）：最小代价排序（相邻交换）

4.3.2 任务分配：双序列匹配

最大化完成任务数（双指针）

经典题（USACO Silver）：配对——排列不等式实战

贪心模拟（USACO Bronze）：奶牛信号

4.3.3 区间合并

4.3.4 字典序构造贪心

经典题：删除 K 个数字得到最小数（字典序最小构造）

经典题：最少跳跃次数

经典题：买卖股票最大利润（贪心版）

4.3.5 中位数贪心——「均分」与「聚集」

经典题一：一维仓库选址

经典题二：均分纸牌（前缀和 + 中位数）

练习题

题目 4.3.1 — USACO 2016 December Bronze：统计干草堆

题目 4.3.2 — USACO 2019 February Bronze：睡觉奶牛排序

题目 4.3.3 — 任务调度器 🟡 中等