A 班 第 2 课：专题二：排序与贪心

适用对象： 已完成第 1 课（复赛规则 + 枚举与模拟）的同学 使用方式： 自学讲义。例题必须自己动手写一遍，不许只看 学完本课，你应该能：

1. 熟练使用 sort 的三种姿势：默认升序、降序、结构体自定义排序
2. 说清"贪心"是什么，会用交换法检验一个贪心策略靠不靠谱
3. 独立完成排队接水、纪念品分组两道例题
4. 挑战一道 CSP-J 复赛 T2 真题（公路）

使用说明：

1. sort 三件套（20 分钟）

GESP 里你已经用过 sort。复赛里它是出场率最高的函数，必须闭着眼写对。它的复杂度是 O(n log n)——对照第 1 课的预算表，n ≤ 10⁶ 随便排。

1.1 姿势一：默认升序

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

int main() {
    int a[5] = {42, 7, 19, 7, 88};
    sort(a, a + 5);
    for (int i = 0; i < 5; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

输出：7 7 19 42 88

⚠️ sort(a, a + n) 的第二个参数是最后一个元素的下一位（左闭右开）。数组从下标 0 存了 n 个数，就写 a + n；如果你习惯从下标 1 存到 n，要写 sort(a + 1, a + n + 1)。每年都有人在这里少排或多排一个数。

1.2 姿势二：降序

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

int main() {
    int a[5] = {42, 7, 19, 7, 88};
    sort(a, a + 5, greater<int>());
    for (int i = 0; i < 5; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

输出：88 42 19 7 7

greater<int>() 是现成的"从大到小"比较器，末尾的 () 别丢。

1.3 姿势三：结构体 + 自定义 cmp

复赛题的数据往往是"捆绑"的：一个学生有姓名和分数，排序时要整行一起动。这时用结构体 + 自己写的比较函数：

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

struct Student {
    int id;      // 学号
    int score;   // 分数
};

bool cmp(Student x, Student y) {
    return x.score > y.score;   // 分数高的排前面
}

int main() {
    Student s[3] = {{1, 80}, {2, 95}, {3, 88}};
    sort(s, s + 3, cmp);
    for (int i = 0; i < 3; i++) {
        cout << s[i].id << " " << s[i].score << endl;
    }
    return 0;
}

输出：

2 95
3 88
1 80

cmp(x, y) 的读法：返回 true 表示"x 应该排在 y 前面"。想按什么规则排，就把那个规则写成一句 return。

多关键字排序（分数相同再比学号）就在 cmp 里加一层：

bool cmp(Student x, Student y) {
    if (x.score != y.score) return x.score > y.score;  // 先比分数，高的在前
    return x.id < y.id;                                // 分数一样，学号小的在前
}

⚠️ cmp 里永远不要写 <= 或 >=。 两个元素"相等"时 cmp 必须返回 false，写 <= 在某些数据下会让程序直接崩溃（RE）。这是隐藏极深的考场炸弹，记成铁律：cmp 只写 < 和 >。

📝 sort 三件套： sort(a, a+n) 升序；sort(a, a+n, greater<int>()) 降序；sort(a, a+n, cmp) 自定义。

2. 贪心：每步都拿眼前最好的（10 分钟）

贪心：把问题拆成一步一步，每一步都选当前看起来最优的，不回头。

贪心的代码通常很短，难点在两个问题上：

1. 按什么顺序处理？ ——绝大多数贪心题第一步都是排序。
2. 这么贪真的对吗？ ——复赛不要求证明，但你需要说服自己。最实用的办法是交换法：

假设答案里有相邻的两步不符合我的贪心策略，把它们交换一下，看结果会不会变差。如果交换后不可能更差，说明按贪心顺序来至少不吃亏——策略成立。

还有一个反向自检：举反例。花 2 分钟想一组小数据故意刁难自己的策略，找不到反例再动手写码。贪心题写错的代价是"全 WA"而不是"部分分"，动笔前多想两分钟很值。

📝 贪心两问：要不要先排序？交换相邻两步会不会更差？

3. 例题一：排队接水（15 分钟）

n 个人在一个水龙头前排队接水，第 i 个人接水需要 tᵢ 分钟（1 ≤ n ≤ 1000，1 ≤ tᵢ ≤ 100）。安排一个排队顺序，使所有人等待时间的总和最小（等待时间 = 排在他前面所有人的接水时间之和，不含自己）。 输出两行：第一行是排队顺序（每个人的编号）；第二行是最小的平均等待时间，保留 2 位小数。接水时间相同的人，编号小的排前面。

输入样例：
3
3 1 2

输出样例：
2 3 1
1.33

题目名：water

第一步：猜贪心。 一个人接水的时间，会被排在他后面的每一个人等一遍。接水慢的人排得越靠前，拖累的人越多——所以接水快的人排前面，按 tᵢ 升序排。

第二步：交换法验证。 假设相邻两人 x 在前、y 在后，且 tₓ > t_y（违反策略）。交换他们，两人之外所有人的等待不变；x、y 内部：交换前 y 多等 tₓ，交换后 x 多等 t_y，因为 t_y < tₓ，总等待变小了。所以"慢的在前"总能通过交换改进——升序排就是最优。✓

第三步：写码。 要输出编号，所以时间和编号得捆绑成结构体：

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

struct Person {
    int t;    // 接水时间
    int id;   // 编号
};

bool cmp(Person x, Person y) {
    if (x.t != y.t) return x.t < y.t;   // 时间短的在前
    return x.id < y.id;                 // 时间相同，编号小的在前
}

int main() {
    freopen("water.in", "r", stdin);
    freopen("water.out", "w", stdout);
    int n;
    cin >> n;
    Person p[1005];
    for (int i = 0; i < n; i++) {
        cin >> p[i].t;
        p[i].id = i + 1;
    }
    sort(p, p + n, cmp);
    long long wait = 0, total = 0;      // wait: 当前这个人要等多久
    for (int i = 0; i < n; i++) {
        cout << p[i].id << " ";
        total += wait;                  // 累加每个人的等待时间
        wait += p[i].t;                 // 他接完水，后面的人多等 t
    }
    cout << endl;
    printf("%.2f\n", (double)total / n);
    return 0;
}

样例验证：升序后顺序是 2(1 分钟)、3(2 分钟)、1(3 分钟)；等待 0 + 1 + 3 = 4，平均 4 ÷ 3 = 1.33 ✓

⚠️ 保留 2 位小数用 printf("%.2f\n", x)，x 必须是小数——total / n 是整数除法，先 (double)total 转成小数再除。

4. 例题二：纪念品分组（NOIP 2007 普及组 T2）（20 分钟）

有 n 件纪念品，第 i 件价格 pᵢ。要把它们分组，每组最多 2 件，且每组价格之和不超过 w。求最少分几组。 （1 ≤ n ≤ 30000，0 < pᵢ ≤ w ≤ 200）

输入样例：
100
9
90 20 20 30 50 60 70 80 90

输出样例：
6

题目名：group（输入第一行是 w，第二行是 n，接下来是 n 个价格）

第一步：猜贪心。 想省组数，就要尽量两两配对。谁和谁配？最便宜的配最贵的：如果当前最贵的连最便宜的都带不动（和超过 w），那它谁也带不动，只能自己一组。

第二步：交换法验证。 若最贵的 R 能和最便宜的 L 配对，却让 L 去配了别人 x（把 R 单放或另配）：把 x 和 R 交换位置，L+R ≤ w 依然成立，x 换到的搭档只会更便宜、更不会超——组数不变或更少。策略成立。✓

第三步：写码——双指针。 排序后左指针 l 指最便宜、右指针 r 指最贵，相向移动：

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

int main() {
    freopen("group.in", "r", stdin);
    freopen("group.out", "w", stdout);
    int w, n;
    cin >> w >> n;
    int p[30005];
    for (int i = 0; i < n; i++) cin >> p[i];
    sort(p, p + n);
    int l = 0, r = n - 1, groups = 0;
    while (l <= r) {
        if (p[l] + p[r] <= w) {
            l++;                // 最便宜的搭上车了
            r--;
        } else {
            r--;                // 最贵的谁也带不动，自己一组
        }
        groups++;               // 不管哪种情况，都用掉一个组
    }
    cout << groups << endl;
    return 0;
}

样例验证：排序后 20 20 30 50 60 70 80 90 90。20+90 超 → 90 单独；20+90 超 → 90 单独；20+80=100 ✓ 配对；20+70=90 ✓ 配对；30+60=90 ✓ 配对；剩 50 单独。共 6 组 ✓

⚠️ while (l <= r) 的等号别丢：l == r 时中间还剩一个人没分组。

📝 双指针框架：排序 → l 最小端、r 最大端 → 能配就 l++, r--，不能配就动一头 → while (l <= r)。

5. 本课练习（15 分钟起步，剩下的当课后作业）

每题按考场格式建文件夹、写 freopen（文件名用题目名）。

⭐ 热身 1：纸上手排（不用电脑）

数组 {15, 3, 99, 3, 47}，写出下面两行代码各自的输出：

1. sort(a, a + 5);
2. sort(a, a + 5, greater<int>());

⭐ 热身 2：前三名（题目名 top3）

输入 n（3 ≤ n ≤ 1000）和 n 个互不相同的整数，输出其中最大的 3 个，从大到小，空格分隔。

输入样例：
5
70 85 60 92 88

输出样例：
92 88 85

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

int main() {
    freopen("top3.in", "r", stdin);
    freopen("top3.out", "w", stdout);
    int n;
    cin >> n;
    int a[1005];
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n, greater<int>());
    cout << a[0] << " " << a[1] << " " << a[2] << endl;
    return 0;
}

⭐⭐ 实战：奖学金（NOIP 2007 普及组 T1，题目名 reward）

n 个学生（1 ≤ n ≤ 300），学号为 1~n，每人有语文、数学、英语三科成绩。按总分从高到低排名；总分相同按语文从高到低；还相同则学号小的在前。输出前 5 名的学号和总分。

输入样例：
6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98

输出样例：
6 265
4 264
3 258
2 244
1 237

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

struct Student {
    int id, chinese, total;
};

bool cmp(Student x, Student y) {
    if (x.total != y.total) return x.total > y.total;        // 1. 总分高的在前
    if (x.chinese != y.chinese) return x.chinese > y.chinese; // 2. 语文高的在前
    return x.id < y.id;                                       // 3. 学号小的在前
}

int main() {
    freopen("reward.in", "r", stdin);
    freopen("reward.out", "w", stdout);
    int n;
    cin >> n;
    Student s[305];
    for (int i = 0; i < n; i++) {
        int c, m, e;
        cin >> c >> m >> e;
        s[i].id = i + 1;
        s[i].chinese = c;
        s[i].total = c + m + e;
    }
    sort(s, s + n, cmp);
    for (int i = 0; i < 5; i++) {
        cout << s[i].id << " " << s[i].total << endl;
    }
    return 0;
}

⭐⭐⭐ 冲刺：公路（CSP-J 2023 T2，题目名 road）

公路上一字排开 n 个站点，站点 i 和 i+1 之间距离 vᵢ 公里。你开车从站点 1 出发去站点 n，出发时油箱是空的。每个站点都卖油，站点 i 的油价是 aᵢ 元/升，只能按整数升购买，油箱容量无限。每升油恰好能走 d 公里。求到达站点 n 的最少花费。

数据范围：1 ≤ n ≤ 10⁵，1 ≤ d, vᵢ, aᵢ ≤ 10⁵。其中约 25% 的数据 n ≤ 8；约 50% 的数据 n ≤ 10³。

输入样例：
5 4
10 10 10 10
9 8 9 6 5

输出样例：
79

（最优方案：在站点 1 买 3 升，站点 2 买 5 升，站点 4 买 2 升，花费 3×9 + 5×8 + 2×6 = 79。）

先自己想 15 分钟再看提示。想不出满分做法时，回忆第 1 课的部分分策略：n ≤ 10³ 的 50% 数据，容许你怎么写？

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

long long v[100005], a[100005];

int main() {
    freopen("road.in", "r", stdin);
    freopen("road.out", "w", stdout);
    long long n, d;
    cin >> n >> d;
    for (int i = 1; i <= n - 1; i++) cin >> v[i];
    for (int i = 1; i <= n; i++) cin >> a[i];
    long long ans = 0, leftKm = 0, minp = a[1];
    for (int i = 1; i <= n - 1; i++) {
        if (a[i] < minp) minp = a[i];       // 目前见过的最低油价
        if (v[i] > leftKm) {                // 存油不够走这一段
            long long need = v[i] - leftKm;
            long long liters = (need + d - 1) / d;   // 向上取整
            ans += liters * minp;           // 按最低价买单
            leftKm += liters * d;
        }
        leftKm -= v[i];                     // 走掉这一段
    }
    cout << ans << endl;
    return 0;
}

本课要点速查

sort 三件套：

sort(a, a + n);                    // 升序
sort(a, a + n, greater<int>());    // 降序
sort(a, a + n, cmp);               // 自定义（结构体必用）

cmp 模板（多关键字）：

bool cmp(Student x, Student y) {
    if (x.total != y.total) return x.total > y.total;  // 每层：不等就分胜负
    return x.id < y.id;                                // 相等就交给下一层
}

双指针框架： 排序 → l 最小端、r 最大端 → while (l <= r) 相向移动。

其他新零件：

贪心两问： 要不要先排序？交换相邻两步会不会更差？（外加：能不能举出反例？）

cmp 铁律： 只写 < 和 >，永远不写 <=、>=。

结束前的自我检查

1. 合上讲义，把 sort 三种写法和多关键字 cmp 模板默写出来
2. 排队接水、纪念品分组两道例题不看答案重写一遍，样例验证通过
3. 用交换法向别人讲清楚："接水为什么快的人排前面？"
4. 公路这道 T2 至少完成"n ≤ 10³ 的 50 分暴力"；满分做法看懂提示后独立写出更好