贪心应用排序不等式和绝对值不等式

作者： 作者的头像   huolong , 时间：2026-09-26 10:51:34 , 所有人可见, 阅读  36

既然你提到了排序不等式和绝对值不等式，这两者确实是 OI/CF 贪心题中最核心、最能直接决定代码正确性的数学基石。

我们可以把这两个经典不等式在 Codeforces 中的应用进行具象化的剖析，并给出标准的数学思维链和 C++ 代码。

一、 绝对值不等式模型：从“货仓选址”到区间重合

1. 数学原理剖析

  • 一维绝对值和最小（中位数定理）： $$\sum_{i=1}^{n} |a_i - x| \text{ 取最小值 } \iff x = \text{中位数}$$
  • 绝对值三角不等式应用： 对于形如 $|x - a_i|$ 的累加，如果在数轴上有多段区间或多个点，往往通过确定中心点（中位数）将原本复杂的绝对值表达式分段去绝对值。

2. 经典 CF 变体模型： Meeting / 均分 / 距离对齐

在 CF 中，绝对值不等式经常被包装成： * “每个人要移动到同一个位置，每单位距离代价不同” $\to$ 带权中位数。 * “在一根数轴上选两个点，使得所有点到最近的那个点的距离之和最小” $\to$ 动态规划 / 双指针结合中位数贪心。

3. 基础货仓选址模板代码 (C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

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

    int n;
    if (!(cin >> n)) return 0;

    vector<long long> x(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }

    // 数学结论：排序后取中位数，距离绝对值和最小
    sort(x.begin(), x.end());
    long long median = x[n / 2];

    long long min_distance_sum = 0;
    for (int i = 0; i < n; ++i) {
        min_distance_sum += abs(x[i] - median);
    }

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

二、 排序不等式模型：从“排队打水”到“耍杂技的牛”

1. 数学原理剖析

排序不等式（Rearrangement Inequality）告诉我们： 设两组数 $a_1 \le a_2 \le \dots \le a_n$ 和 $b_1 \le b_2 \le \dots \le b_n$： * 同向和最大：$\sum a_i b_i$ 当且仅当两组数同向排序（大配大，小配小）时最大。 * 异向和最小：$\sum a_i b_i$ 当且仅当两组数异向排序（大配小）时最小。

而在贪心微扰证明（Exchange Argument）中，更常见的是邻项交换法推导出的自定义排序规则： 假设相邻两项 $i$ 和 $i+1$，如果交换后更优，则推导出排序的关键字。

2. 经典 CF 场景：多任务消耗 / 带有权重的贪心

  • 模型：每个任务有持续时间 $t_i$ 和惩罚系数 $w_i$，先做哪个后做哪个？
  • 推导：考虑相邻两个任务 $i$ 和 $i+1$。 如果先 $i$ 后 $i+1$，代价为：$w_i \cdot t_{i+1}$（或者更复杂的累计代价）。 通过比较 $w_i t_{i+1}$ 与 $w_{i+1} t_i$ 的大小，就能直接用 sort 自定义比较函数（Lambda 表达式）搞定。

3. 经典“排队打水/加工任务”贪心代码 (C++)

假设有 $n$ 个人打水，第 $i$ 个人打水时间为 $t_i$，怎么排队让所有人等待的总时间之和最小？ * 数学直觉：时间短的人先打水，可以让后面所有排队的人少等一会儿。 * 代码实现：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    int n;
    if (!(cin >> n)) return 0;

    vector<long long> t(n);
    for (int i = 0; i < n; ++i) {
        cin >> t[i];
    }

    // 排序不等式应用：升序排列使总等待时间最小
    sort(t.begin(), t.end());

    long long total_wait_time = 0;
    long long accumulated_time = 0;

    for (int i = 0; i < n; ++i) {
        total_wait_time += accumulated_time; // 累加前面的人消耗的时间
        accumulated_time += t[i];
    }

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

三、 总结：OIer 面对数学贪心时的“条件反射”

当你在 Codeforces 遇到一道贪心题，卡住时可以对照以下三步：

  1. 看到绝对值 $|\dots|$：
  2. 如果是求和 $\sum |x - a_i|$ $\to$ 立刻排序取中位数。
  3. 如果是二维距离 $|x_1 - x_2| + |y_1 - y_2|$ $\to$ 考虑切比雪夫距离转换（坐标旋转 $45^\circ$）。
  4. 看到多元素配对 / 顺序先后影响总代价：
  5. 不要盲目 DFS 或 DP。先写出相邻两项 $i$ 和 $i+1$ 交换前后的不等式（Exchange Argument）。
  6. 移项化简，得出 bool cmp 比较函数的依据，直接 sort 解决。
  7. 看到最大化乘积 $\prod$：
  8. 立刻取对数 ($\ln$) 转化为加法求和，或者应用均值不等式（AM-GM）寻找极端平衡点（如尽量平均分配或构造成 $e$ 附近的数）。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com