K03 排序与贪心 + 二分与倍增（第二轮系统课 · 第 3 次）

本次两个模块：

一、M5 排序与贪心

盲写（15 分钟，合上讲义）

输入 n（n ≤ 10⁵）和 k，接下来 n 行，每行一个学生的学号和总分。按总分从高到低排序，总分相同按学号从小到大，输出前 k 名的学号和总分。

输入：

4 3
3 90
1 95
2 90
4 80

输出：1 95 / 2 90 / 3 90（每个一行）

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

struct Stu {
    int id, score;
};

bool cmp(const Stu& a, const Stu& b) {
    if (a.score != b.score) return a.score > b.score;   // 第一关键字：总分降序
    return a.id < b.id;                                 // 第二关键字：学号升序
}

Stu s[100005];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> s[i].id >> s[i].score;
    sort(s, s + n, cmp);
    for (int i = 0; i < k; i++) cout << s[i].id << " " << s[i].score << endl;
    return 0;
}

⚠️ cmp 里只能用 < 或 >，绝不能用 <= 或 >=。 用了等号，遇到相等的元素 sort 可能越界崩溃——而且样例常常测不出来。

1.1 复用：先翻旧讲义

什么时候用哪种排序：

1.2 贪心：三类最常见的题型

贪心 = 每一步都选当前看起来最好的。难点不在写，在于判断"这样选到底对不对"。CSP-J 里的贪心题，九成是下面三类之一：

区间选择（最多选几个互不重叠的区间）手推一遍：

按右端点排好（就是上表的顺序），维护"上一个选中区间的右端点" last：

1. [1,3]：开头就选，last = 3
2. [2,5]：左端点 2 < 3，重叠，跳过
3. [4,6]：4 ≥ 3，选，last = 6
4. [6,8]：6 ≥ 6（端点相接算不算重叠，要看题目），选，last = 8
5. [5,9]：5 < 8，跳过

答案是 3 个。

⚠️ 为什么按右端点，不按左端点？ 按左端点排序，[1,100] 排在最前面会被先选，一个区间就占满了。右端点小 = 结束得早 = 给后面留的空间多。

1.3 "交换一下会不会更好"

拿不准贪心对不对时，用这招检查：假设最优答案里有两个相邻的元素顺序和你的贪心不一样，把它们交换，答案会不会变差？

排队接水：两个人接水时间是 a < b。a 在前，两人总等待是 a + (a + b)；b 在前是 b + (b + a)。前者更小，所以时间短的应该排前面。

📝 考场上不需要写证明，但要在纸上用两个数算一下。 算不出来就写暴力拿部分分，别赌。

二、M6 二分与倍增

盲写（15 分钟，合上讲义，不许用 lower_bound）

输入 n 个从小到大排好的整数，再输入 m 个询问，每个询问一个 x，输出第一个 ≥ x 的数的下标（从 1 开始），没有则输出 -1。

输入 5 3 / 1 3 3 5 7 / 3 4 8 → 输出 2 4 -1

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

int a[1000005];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    while (m--) {
        int x;
        cin >> x;
        int l = 1, r = n, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (a[mid] >= x) { ans = mid; r = mid - 1; }   // 满足条件：记下来，继续往左找更靠前的
            else l = mid + 1;
        }
        cout << ans << " ";
    }
    cout << endl;
    return 0;
}

📝 这个写法的好处：ans 专门记答案，循环条件永远是 l <= r，不用纠结 r = mid 还是 r = mid - 1。 二分答案也用同一个骨架（L03）。

2.1 复用：先翻旧讲义

2.2 lower_bound 和 upper_bound

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

int main() {
    int a[] = {1, 3, 3, 5, 7};
    int n = 5;
    int x = 3;
    int L = lower_bound(a, a + n, x) - a;      // 减去数组名，得到下标
    int R = upper_bound(a, a + n, x) - a;
    cout << L << " " << R << " " << R - L << endl;
    int y = 8;
    int p = lower_bound(a, a + n, y) - a;
    cout << (p == n ? "not found" : "found") << endl;   // 找不到时返回 n（末尾后面一格）
    return 0;
}

⚠️ 两个前提：①数组必须已经排好序；②找不到时返回的是末尾后面那一格（下标 n），用之前要先判断，否则越界。

2.3 二分的四个坑

2.4 倍增：一步跳 1、2、4、8……

倍增的想法：要走 b 步，不一步一步走，而是按 1、2、4、8…… 这些"2 的幂"来跳。 任何一个数都能拆成若干个 2 的幂之和（这就是二进制，S1），所以最多跳 log b 次。

最经典的应用是快速幂：算 a^b mod p，b 可以到 10⁹ 甚至 10¹⁸。

一步一步乘要 b 次，超时。快速幂的想法：

• a¹、a²、a⁴、a⁸……每一个都是前一个的平方，算一次乘法就能得到下一个
• 比如 b = 13 = 8 + 4 + 1（二进制 1101），a¹³ = a⁸ × a⁴ × a¹
• 看 b 的每一个二进制位：是 1 就把当前的 a^(2^k) 乘进答案

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

// 计算 a^b mod p，O(log b)
long long qpow(long long a, long long b, long long p) {
    long long ans = 1 % p;           // p=1 时答案是 0，这个 % p 不能省
    a %= p;
    while (b > 0) {
        if (b & 1) ans = ans * a % p;    // 这一位是 1：乘进答案
        a = a * a % p;                   // a 变成 a^2、a^4、a^8 ……
        b >>= 1;                         // 看下一位
    }
    return ans;
}

int main() {
    cout << qpow(2, 10, 1000) << endl;
    cout << qpow(3, 1000000000, 1000000007) << endl;
    cout << qpow(5, 0, 1) << endl;
    return 0;
}

⚠️ 两个坑：①ans * a 和 a * a 都可能到 p² ≈ 10¹⁸，必须 long long，而且 p 不能超过约 3×10⁹；②**1 % p 比 1 更保险**——如果题目允许 p = 1，任何数模 1 都是 0，而 b = 0 时循环一次都不进，直接返回初值。（P1226 保证 p ≥ 2，但别的题不一定。）

📝 倍增和 K01 的优秀的拆分是同一件事：把一个数拆成 2 的幂之和，就是看它的二进制哪几位是 1。

三、课堂题与小测

四、课后作业

五、30 秒自测

1. cmp 里为什么不能写 <=？
2. 区间选择为什么按右端点排序？
3. upper_bound - lower_bound 算的是什么？
4. 二分答案前要先确认题目有什么性质？
5. 快速幂为什么是 O(log b)？ans 的初值为什么写 1 % p？

本次打卡：M5 ①、M6 ①（两道盲写）；作业 AC 后打 ②③。