贪心的几大模型

作者： 作者的头像   huolong , 时间：2026-09-26 10:43:03 , 所有人可见, 阅读  28

下面挑选了三个在 CF 中极具代表性的模型：① 中位数绝对值距离模型、② 曼哈顿距离转切比雪夫距离（坐标系旋转）、③ 排序不等式（柯西/内积贪心），并附带详细的题目背景与 C++ 代码。

模型一：中位数绝对值距离模型（绝对值和最小）

📌 CF 经典原型：CF 1006C / 类似均分或绝对值对齐问题

  • 数学模型：给定数轴上的 $n$ 个点 $a_1, a_2, \dots, a_n$，找一个点 $x$，使得 $\sum_{i=1}^n |a_i - x|$ 最小。
  • 数学结论：$x$ 取这组数的中位数（Median）时取得最小值。如果要求所有数变为同一个数且只能做 $+1/-1$ 操作，代价和就是所有点到中位数的距离和。

💡 进阶变体（带权中位数 / 移动代价）：

如果每个人移动单位距离的代价不同，或者有限制。我们看一个经典的“均分纸牌 / 搬砖问题”。

📄 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> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // 1. 排序，准备找中位数
    sort(a.begin(), a.end());

    // 2. 中位数作为目标值（若n为偶数，取a[n/2]或a[n/2-1]均可）
    long long median = a[n / 2];

    // 3. 计算所有点到中位数的绝对值距离和
    long long total_cost = 0;
    for (int i = 0; i < n; ++i) {
        total_cost += abs(a[i] - median);
    }

    cout << total_cost << "\n";

    return 0;
}

模型二：曼哈顿距离转切比雪夫距离（坐标系旋转）

📌 CF 经典原型：CF 1093G - Multidimensional Queries / 二维平面曼哈顿距离最值

  • 数学背景：在二维平面上，点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 的曼哈顿距离是 $|x_1 - x_2| + |y_1 - y_2|$。由于有绝对值的存在，直接维护或贪心极其痛苦。
  • 数学旋转变换： 定义新坐标：$u = x + y$, $v = x - y$。 那么曼哈顿距离 $\max(|x_1 - x_2|, |y_1 - y_2|)$ 在新坐标系下变成了： $\max(|u_1 - u_2|, |v_1 - v_2|)$ （这就是切比雪夫距离）。 把“绝对值和”变成了独立的“横坐标差的最大值”和“纵坐标差的最大值”。

📄 C++ 代码演示（坐标变换的核心思想）：

假设我们要找平面上任意两点间的最大曼哈顿距离：

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

using namespace std;

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

    int n;
    cin >> n;

    long long max_u = -2e18, min_u = 2e18;
    long long max_v = -2e18, min_v = 2e18;

    for (int i = 0; i < n; ++i) {
        long long x, y;
        cin >> x >> y;

        // 核心数学变换：曼哈顿 -> 切比雪夫
        long long u = x + y;
        long long v = x - y;

        max_u = max(max_u, u);
        min_u = min(min_u, u);
        max_v = max(max_v, v);
        min_v = min(min_v, v);
    }

    // 旋转后，最大曼哈顿距离就等于切比雪夫距离的最大差值
    long long ans = max(max_u - min_u, max_v - min_v);
    cout << ans << "\n";

    return 0;
}

模型三：排序不等式与内积贪心（Rearrangement Inequality）

📌 CF 经典原型：CF 1400C / 类似任务分配、构造最大/最小匹配

  • 数学模型：给定两个数组 $A = [a_1, a_2, \dots, a_n]$ 和 $B = [b_1, b_2, \dots, b_n]$。你可以任意重排 $B$。
  • 要使内积 $\sum a_i b_i$ 最大化：必须让 $A$ 和 $B$ 同向排序（大的配大的，小的配小的）。
  • 要使内积 $\sum a_i b_i$ 最小化：必须让 $A$ 和 $B$ 异向排序（大的配小的，极端的配相反的）。

📄 C++ 代码示例（使内积最大的贪心匹配）：

#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> a(n), b(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];

    // 排序不等式核心：同向排序使得乘积之和最大
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    long long max_product_sum = 0;
    for (int i = 0; i < n; ++i) {
        max_product_sum += a[i] * b[i]; // 大的乘大的，小的乘小的
    }

    // 如果要求最小，则将 b 逆序或者让大配小：
    // sort(b.rbegin(), b.rend()); 即可

    cout << max_product_sum << "\n";

    return 0;
}

🧠 总结

  • 当看到 $|x-a| + |x-b|$，想到中位数 / 凸函数。
  • 当看到 $|x_1 - x_2| + |y_1 - y_2|$（曼哈顿距离），立刻想到 $u=x+y, v=x-y$ 坐标系旋转。
  • 当看到 两组数相乘求最值，立刻想到 排序不等式（同向最大，异向最小）。

在 CF 中，代码通常只有十几行到几十行，最难的永远是上面这层数学模型的识别与转换。掌握了这些模型，再刷贪心题就会有一种“降维打击”的感觉！

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