算法基础篇：（九）贪心算法拓展之推公式：从排序规则到最优解的推导艺术

前言

在算法世界里，贪心算法一直以 “简单粗暴却高效” 的特质让人又爱又恨。简单的贪心问题能让你一眼看穿思路，而复杂问题却常常让人困惑 “为什么这样选就是最优”。其中，“推公式” 作为贪心算法的重要拓展方向，更是将 “局部最优推导全局最优” 的思想发挥到了极致 —— 它不依赖固定模板，而是通过数学推导找到排序规则，再基于规则对问题元素排序，最终得到最优解。今天，我们就来深入拆解贪心算法中的推公式思想，从原理到实践，结合经典例题带你掌握这门 “推导艺术”。

一、推公式思想的核心：排序规则是如何诞生的？

1.1 贪心与推公式的关联

贪心算法的本质是 “每一步都做出当前最优选择，最终期望得到全局最优”。但 “最优选择” 的标准往往模糊不清，尤其是当问题涉及多个元素的顺序排列时 —— 比如 “如何排列多个数字得到最大整数”“如何安排奶牛赶回去的顺序使损失最小”，此时直接判断 “谁先谁后” 并不直观。

而推公式的核心作用，就是将 “最优顺序” 这个模糊问题，转化为可量化的数学判断标准。它的核心逻辑是：

1. 问题的最优解依赖于元素的排列顺序；
2. 交换任意两个相邻元素，只会影响这两个元素的贡献，不会影响其他元素；
3. 通过比较 “交换前” 和 “交换后” 的总贡献，推导得出 “谁应该在前” 的数学条件；
4. 将这个数学条件作为排序规则，对所有元素排序，得到最优解。

简单来说，推公式就是通过相邻元素的交换论证，找到排序的数学依据。这种思想的魅力在于，它无需枚举所有可能的排列（因为复杂度极高），而是通过数学推导将问题转化为 “排序问题”，时间复杂度可降至 O (nlogn)，高效且通用。

1.2 推公式的正确性基础：全序关系

为什么通过相邻元素推导的排序规则，能保证整个序列的最优性？这背后依赖于离散数学中的 “全序关系”—— 如果排序规则满足自反性、反对称性和传递性，那么按照该规则排序后的序列，就是全局最优序列。

在贪心推公式问题中，我们只需证明：对于任意三个元素 a、b、c，如果 a 应该在 b 前面，b 应该在 c 前面，那么 a 一定应该在 c 前面（传递性）。而这个传递性，往往会通过推导的数学规则自然满足。后续例题中，我们会通过具体推导验证这一点。

1.3 推公式的通用步骤

掌握推公式的思想，无需死记硬背，只需遵循以下四步：

1. 明确问题目标：是最大化总收益、最小化总损失，还是其他最优指标；
2. 假设相邻元素：取出序列中任意两个相邻元素 x 和 y，分析它们的排列顺序对目标的影响；
3. 推导排序条件：计算 “x 在前、y 在后” 和 “y 在前、x 在后” 两种情况下的目标贡献，比较两者大小，得出 “哪种排列更优” 的数学条件；
4. 验证规则有效性：确保推导的条件满足全序关系（尤其是传递性），然后用该规则对所有元素排序，得到最优解。

接下来，我们通过三个经典例题，一步步拆解推公式的实践过程，从简单到复杂，带你吃透每一个细节。

二、经典例题拆解：推公式的实战演练

2.1 例题 1：拼数（洛谷 P1012）—— 最大化拼接整数

题目链接：https://www.luogu.com.cn/problem/P1012

题目描述

设有 n 个正整数，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。例如输入 3 个数字 13、312、343，输出应为 34331213。

问题分析

目标是 “最大化拼接后的整数”，核心是确定两个数字 x 和 y 的排列顺序 —— 是 x 在前、y 在后（拼接为 xy），还是 y 在前、x 在后（拼接为 yx）？

由于数字拼接的结果是字符串，直接比较两个数字的大小没有意义（比如 13 和 312，13<312，但 13312<31213）。因此，我们需要通过推公式找到 “xy 和 yx 哪个更大” 的判断标准。

推公式过程

设 x 和 y 对应的字符串为 s 和 t，我们需要比较 s+t 和 t+s 的大小：

• 如果 s+t > t+s：说明 x 在前、y 在后的拼接结果更大，因此 x 应该排在 y 前面；
• 如果 s+t < t+s：说明 y 在前、x 在后的拼接结果更大，因此 y 应该排在 x 前面；
• 如果 s+t = t+s：两者顺序不影响结果，可任意排列。

这个推导过程非常直接，因为交换 x 和 y 的位置，只会改变 x 和 y 拼接后的结果，不会影响其他元素的拼接（比如序列 a、x、y、b，交换 x 和 y 后，a 与 x/y 的拼接、y/x 与 b 的拼接都不受影响，仅 x 和 y 之间的拼接变化）。

正确性验证

该规则是否满足传递性？假设对于三个字符串 s、t、u，有 s+t > t+s 且 t+u > u+t，那么一定有 s+u > u+s 吗？

举个例子：s="343"，t="312"，u="13"

• 343312 > 312343（s+t > t+s）
• 31213 > 13312（t+u > u+t）
• 34313 > 13343（s+u > u+s）

显然满足传递性。因此，该排序规则是有效的。

C++ 代码实现

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

const int N = 25;
int n;
string a[N];

// 自定义排序规则：s+t > t+s 则s在前
bool cmp(string& s, string& t) {
    return s + t > t + s;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n, cmp);
    
    // 特殊情况：如果排序后第一个元素是"0"，说明所有元素都是0
    if (a[1] == "0") {
        cout << 0 << endl;
        return 0;
    }
    
    for (int i = 1; i <= n; i++) {
        cout << a[i];
    }
    cout << endl;
    return 0;
}

代码说明

1. 由于 n 的范围是≤20，O (nlogn) 的排序复杂度完全可接受；
2. 特殊处理全 0 的情况（比如输入 0、0、0，输出应为 0 而非 000）；
3. 核心是自定义排序函数 cmp，直接使用推导的规则 s+t > t+s。

2.2 例题 2：保卫花园（USACO07JAN）—— 最小化奶牛吃草损失

题目链接：https://www.luogu.com.cn/problem/P2878

题目描述

有 n 头奶牛在花园里吃花，每头奶牛距离牛圈 Ti 分钟（FJ 往返需要 2×Ti 分钟），每分钟吃 Di 朵花。FJ 每次只能赶一头奶牛回牛圈，在赶奶牛的过程中，其他奶牛继续吃花。求最少的花被吃掉的数量。

问题分析

目标是 “最小化总损失”，核心是确定赶奶牛的顺序。假设我们有两头奶牛 A（T1, D1）和 B（T2, D2），需要判断先赶 A 还是先赶 B，总损失更小。

推公式过程

我们需要计算两种顺序的总损失，然后比较大小。

首先明确：赶奶牛的过程中，未被赶的奶牛会持续吃花。因此，赶某一头奶牛的 “时间成本” 会影响所有未被赶的奶牛的损失。

设当前已经花费的时间为 T（即在此之前，FJ 已经花费了 T 分钟赶其他奶牛），现在考虑 A 和 B 的顺序：

顺序 1：先赶 A，再赶 B

• 赶 A 的往返时间：2×T1 分钟。在这 2×T1 分钟内，B 一直在吃花，损失为 2×T1×D2；
• 赶 A 期间，A 本身已经被赶走，不再吃花（因为 FJ 赶它的时候，它已经停止吃花了）；
• 赶完 A 后，赶 B 的往返时间：2×T2 分钟。此时没有其他奶牛（假设只有 A 和 B），损失为 0；
• 此外，在赶 A 和 B 之前，A 和 B 已经吃了 T 分钟的花，损失为 T×(D1+D2)；
• 总损失（仅考虑 A 和 B 的顺序影响，不考虑之前的 T 分钟）：2×T1×D2。

顺序 2：先赶 B，再赶 A

• 同理，赶 B 的往返时间 2×T2 分钟内，A 一直在吃花，损失为 2×T2×D1；
• 总损失（仅考虑顺序影响）：2×T2×D1。

我们的目标是选择总损失更小的顺序，即比较 2×T1×D2 和 2×T2×D1 的大小（2 是常数，可忽略）：

• 如果 T1×D2 < T2×D1：顺序 1（先赶 A）的损失更小，因此 A 应该排在 B 前面；
• 如果 T1×D2 > T2×D1：顺序 2（先赶 B）的损失更小，因此 B 应该排在 A 前面；
• 如果相等：顺序不影响。

正确性验证

该规则是否满足传递性？假设对于三头奶牛 A、B、C，有 T1×D2 < T2×D1 且 T2×D3 < T3×D2，那么是否有 T1×D3 < T3×D1？

证明：由 T1×D2 < T2×D1 → T1/T2 < D1/D2；

由 T2×D3 < T3×D2 → T2/T3 < D2/D3；

两式相乘得：(T1/T2)×(T2/T3) < (D1/D2)×(D2/D3) → T1/T3 < D1/D3 → T1×D3 < T3×D1。

传递性成立！因此，该排序规则是有效的。

C++ 代码实现

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

typedef long long LL;
const int N = 1e5 + 10;
int n;

struct Cow {
    int t; // 距离牛圈的时间（单程）
    int d; // 每分钟吃花的数量
} a[N];

// 排序规则：T1*D2 < T2*D1 → A在前
bool cmp(Cow& x, Cow& y) {
    return (LL)x.t * y.d < (LL)y.t * x.d;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].t >> a[i].d;
    }
    sort(a + 1, a + 1 + n, cmp);
    
    LL total_loss = 0; // 总损失
    LL time_used = 0;  // 已经花费的时间（用于计算后续奶牛的损失）
    for (int i = 1; i <= n; i++) {
        // 赶当前奶牛的往返时间内，其他未被赶的奶牛继续吃花
        // 未被赶的奶牛是a[i+1..n]，它们的总吃花速度是sum(a[j].d for j=i+1 to n)
        // 但直接计算sum会超时，因此换一种思路：
        // 每头奶牛被其他奶牛“影响”的时间，是在它被赶走之前，FJ花费的总时间
        // 即对于奶牛a[i]，它会在time_used分钟内持续吃花，直到被赶走
        total_loss += (LL)time_used * a[i].d;
        // 赶当前奶牛花费的时间（往返），累加到总时间中
        time_used += 2LL * a[i].t;
    }
    
    cout << total_loss << endl;
    return 0;
}

代码说明

1. 数据范围：n≤1e5，O (nlogn) 排序复杂度可行；
2. 注意数据溢出：t 和 d 的乘积可能超过 int 范围，因此必须使用 long long；
3. 损失计算的优化：避免直接计算未被赶奶牛的总和（O (n²) 超时），而是转换思路 —— 每头奶牛的吃花时间，是它被赶走之前 FJ 已经花费的总时间（time_used），因此总损失为每头奶牛的 d 乘以 time_used，再累加赶它的时间。

2.3 例题 3：奶牛玩杂技（USACO05NOV）—— 最小化最大压扁指数

题目链接：https://www.luogu.com.cn/problem/P1842

题目描述

有 N 头奶牛，每头奶牛的体重为 Wi，力量为 Si。将奶牛摞在一起，每头奶牛的压扁指数等于 “上面所有奶牛的总重量 - 自身力量”。总压扁指数是所有奶牛中最大的压扁指数。求最小的总压扁指数。

问题分析

目标是 “最小化最大压扁指数”，核心是确定奶牛的摞放顺序。假设我们有两头奶牛 A（W1, S1）和 B（W2, S2），需要判断 A 在 B 上面还是 B 在 A 上面，能让最大压扁指数更小。

推公式过程

设 A 和 B 上面的所有奶牛总重量为 W（这部分重量对 A 和 B 的压扁指数影响是固定的，交换 A 和 B 的位置不会改变）。我们分别计算两种顺序的最大压扁指数。

顺序 1：A 在上面，B 在下面

• A 的压扁指数：上面没有奶牛，因此为 W - S1；
• B 的压扁指数：上面有 A，总重量为 W + W1，因此为 (W + W1) - S2；
• 此时的最大压扁指数：max (W - S1, W + W1 - S2)。

顺序 2：B 在上面，A 在下面

• B 的压扁指数：W - S2；
• A 的压扁指数：(W + W2) - S1；
• 此时的最大压扁指数：max (W - S2, W + W2 - S1)。

我们需要选择两种顺序中 “最大压扁指数更小” 的一种。由于 W 是公共项，可将其从所有表达式中减去（不影响大小比较），简化为比较：max (-S1, W1 - S2) 和 max (-S2, W2 - S1)

我们的目标是找到使 max (-S1, W1 - S2) < max (-S2, W2 - S1) 成立的条件，即 A 在 B 上面更优的条件。

为了推导这个条件，我们可以假设最优的排序规则是 W1 + S1 < W2 + S2（后续验证这个假设）。代入具体数值验证：

例：A (10, 3)，B (2, 5)

• W1 + S1 = 13，W2 + S2 = 7 → 13 > 7，因此 B 应该在 A 上面；
• 顺序 1（A 上 B 下）：max (-3, 10-5)=max (-3,5)=5；
• 顺序 2（B 上 A 下）：max (-5,2-3)=max (-5,-1)=-1；
• 显然顺序 2 更优，符合 W1 + S1 > W2 + S2 时 B 在前的规则。

再例：A (2,5)，B (3,3)

• W1 + S1 =7，W2 + S2=6 → 7>6，B 在 A 上面；
• 顺序 1（A 上 B 下）：max (-5,2-3)=max (-5,-1)=-1；
• 顺序 2（B 上 A 下）：max (-3,3-5)=max (-3,-2)=-2；
• 顺序 2 更优，符合规则。

进一步数学推导：假设 W1 + S1 ≤ W2 + S2，证明 max (-S1, W1 - S2) ≤ max (-S2, W2 - S1)。

由于 W1 + S1 ≤ W2 + S2 → W1 - S2 ≤ W2 - S1，且 -S1 ≤ W2 - S1（因为 W2 ≥1）。

同时，W1 + S1 ≤ W2 + S2 → W1 - S2 ≤ -S2（因为 W1 + S1 ≤ W2 + S2 → W1 - S2 ≤ W2 - S1 - S1 + S2？ 此处省略复杂推导，核心结论是：当 W1 + S1 ≤ W2 + S2 时，A 在 B 上面更优）。

因此，排序规则为：按照 W + S 的值从小到大排序，W + S 小的奶牛排在上面。

正确性验证

传递性验证：假设 A、B、C 满足 W1+S1 ≤ W2+S2 且 W2+S2 ≤ W3+S3，则 W1+S1 ≤ W3+S3，传递性成立。因此，该规则是有效的。

C++ 代码实现

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

typedef long long LL;
const int N = 5e4 + 10;
int n;

struct Cow {
    int w; // 体重
    int s; // 力量
} a[N];

// 排序规则：w1 + s1 < w2 + s2 → 排在前面（上面）
bool cmp(Cow& x, Cow& y) {
    return (LL)x.w + x.s < (LL)y.w + y.s;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].w >> a[i].s;
    }
    sort(a + 1, a + 1 + n, cmp);
    
    LL max_pressure = LLONG_MIN; // 最大压扁指数
    LL total_weight = 0;         // 上面所有奶牛的总重量
    for (int i = 1; i <= n; i++) {
        // 当前奶牛的压扁指数 = 上面总重量 - 自身力量
        LL pressure = total_weight - a[i].s;
        // 更新最大压扁指数
        if (pressure > max_pressure) {
            max_pressure = pressure;
        }
        // 将当前奶牛的重量累加到总重量中（为下面的奶牛计算）
        total_weight += a[i].w;
    }
    
    cout << max_pressure << endl;
    return 0;
}

代码说明

1. 数据范围：n≤5e4，O (nlogn) 排序复杂度可行；
2. 初始值设置：max_pressure 设为 LLONG_MIN（避免遗漏负数的最大压扁指数）；
3. 核心逻辑：遍历排序后的奶牛，依次计算每头奶牛的压扁指数，更新最大值，同时累加总重量。

三、推公式思想的通用规律与技巧

3.1 适用场景总结

通过以上三道例题，我们可以总结出推公式思想的适用场景：

1. 问题的最优解依赖于元素的排列顺序（如拼接、安排顺序、摞放顺序等）；
2. 交换任意两个相邻元素，仅影响这两个元素的贡献，不影响其他元素；
3. 元素的贡献可以量化（如拼接后的数值大小、损失的花数、压扁指数等）。

常见的问题类型包括：排列优化（最大化 / 最小化某种指标）、任务调度（安排顺序使总代价最小）、组合优化（如拼接、摞放等）。

3.2 推导技巧

1. 聚焦相邻元素：无需考虑所有元素的排列，只需对比任意两个相邻元素的两种排列方式，简化问题；
2. 忽略公共项：在比较两种排列的贡献时，忽略不随顺序变化的公共项（如前面例题中的 W），简化计算；
3. 验证传递性：推导得出排序规则后，务必验证传递性（可通过数学证明或举例验证），避免规则无效；
4. 处理数据溢出：推导过程中涉及乘法或加法时，注意数据范围，及时使用 long long 避免溢出。

3.3 常见误区

1. 混淆 “排列顺序” 与 “贡献计算”：比如在保卫花园问题中，误将 “赶当前奶牛的时间” 计入当前奶牛的损失，而实际上应计入未被赶奶牛的损失；
2. 忽略特殊情况：比如拼数问题中的全 0 场景，直接输出排序后的结果会得到 “000”，而非 “0”；
3. 未验证传递性：仅凭直觉推导规则，未验证传递性，导致排序后并非最优解；
4. 数据溢出：未使用 long long，导致乘法或加法结果溢出，答案错误。

总结

贪心算法中的推公式思想，是一种 “化繁为简” 的数学智慧 —— 它将复杂的排列优化问题，通过相邻元素的交换论证，转化为清晰的数学排序规则，最终通过排序得到最优解。这种思想不依赖固定模板，核心在于 “推导” 和 “验证”，需要我们具备一定的数学思维和逻辑推理能力。 推公式思想不仅适用于贪心算法，在动态规划、排序算法等领域也有广泛应用。希望你能通过本文的学习，举一反三，在遇到类似问题时，能够快速想到 “推公式” 的思路，用数学推导破解算法难题。 最后，算法学习的核心是 “理解” 和 “实践”。建议大家在看完本文后，重新推导一遍例题的排序规则，然后独立完成拓展练习，加深对推公式思想的理解。如果在推导过程中遇到问题，不妨回到本文的例题，对比思路，找到问题所在。祝你在算法的道路上越走越远！