课堂复习笔记：模拟、贪心与最短路

一、今日知识地图

模块	对应题型	核心能力
基础模拟	时间转换、评分计算、扫雷、煮肠粉	按题意拆步骤，维护变量和状态
数组与网格	三角形小路、扫雷	坐标、方向数组、边界处理
排序与贪心	气球充气	排序后配对，保证局部最优推出整体最优
图论建模	城市、道路、通信线路、牧场	把题意转成点、边、边权
最短路	Floyd、Dijkstra	求两点最短路、单源最短路、所有点最短路
变形最短路	信使、香甜的黄油、最小花费	最远距离、距离总和、乘法权值

---

二、基础模拟：按流程写代码

模拟题最重要的不是算法复杂，而是把题意中的过程按顺序翻译成变量变化。

1. 时间转换

给定总秒数 S，转换成小时、分钟、秒。

hour = S / 3600;
S %= 3600;
minute = S / 60;
second = S % 60;

复习重点：

• / 得到完整单位数量。
• % 得到剩余部分。
• 先算大单位，再算小单位。

---

2. 去最高最低分

5 个分数去掉一个最高分和一个最低分，剩下 3 个分数乘难度系数。

sum += x;
maxs = max(maxs, x);
mins = min(mins, x);
ans = (sum - maxs - mins) * D;

注意：

• 最高分或最低分出现多次时，只去掉一次。
• 答案可能很大，建议用 long long。

---

3. 扫雷棋盘

每个炸弹会影响周围 8 个格子。

方向数组写法：

int dx[8] = {-1,-1,-1,0,0,1,1,1};
int dy[8] = {-1,0,1,-1,1,-1,0,1};

处理思路：

1. 读入炸弹位置，标记为炸弹。
2. 对每个非炸弹格子，统计周围 8 个方向的炸弹数量。
3. 炸弹输出 B，普通格子输出数字。

边界检查：

if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
    // 合法位置
}

---

三、网格与相邻关系

三角形小路

这类题的核心是：每个湿地砖初始贡献 3 条边，如果两块湿地砖相邻，则公共边不需要贴胶带。

基本思想：

答案 = 湿地砖数量 * 3 - 相邻湿地砖公共边数量 * 2

如果用“每块砖检查相邻砖”的方式，每发现一条公共边，可能会被统计两次，所以要统一口径：

• 要么每个方向都检查，公共边每次减 1。
• 要么只检查固定方向，公共边每次减 2。

复习重点：

• 先画图，确定哪些位置真正相邻。
• 三角形上下方向会影响上下两行是否相邻。
• 不要把“看起来挨着”误认为一定有公共边。

---

四、排序与贪心：气球充气

题意模型

有容量为 1,2,3,...,n 的气球，也有 n 个气罐。一个气罐只能配一个气球，不能让任何气球爆炸。

目标：让所有气球中最小充气比例尽量大。

贪心策略

把气罐气量从小到大排序，依次配给容量从小到大的气球。

sort(c + 1, c + n + 1);
for (int i = 1; i <= n; i++) {
    if (c[i] > i) impossible = true;
    ans = min(ans, 1.0 * c[i] / i);
}

为什么这样合理？

• 小气罐应该优先配小容量气球，否则更容易拉低最小比例。
• 如果排序后 c[i] > i，说明第 i 小的气罐连容量 i 的气球都会充爆，更大的气罐只会更危险。

输出：

• 如果会爆炸，输出 -1。
• 否则输出最小比例 ans。

---

五、排队模拟：煮肠粉

这类题有多个“资源”：

• 阿姨：一次只能处理 1 份原材料。
• 肠粉机：有 2 台，每台一次蒸 1 份。
• 学生：第 i 个在 i^2 时刻到达。

模拟变量

cookFree       // 阿姨下一次空闲时间
machine1Free   // 1 号肠粉机下一次空闲时间
machine2Free   // 2 号肠粉机下一次空闲时间

每个学生的处理流程

到达时间 arrive = i * i
原材料开始时间 = max(arrive, cookFree)
原材料结束时间 = 原材料开始时间 + t1
选择更早空闲的肠粉机
蒸煮开始时间 = max(原材料结束时间, machineFree)
完成时间 = 蒸煮开始时间 + t2
等待时间 = 完成时间 - arrive

复习重点：

• 每个资源都要维护“下一次可用时间”。
• 有多个同类资源时，选择最早空闲的那个。
• i*i、总等待时间可能很大，用 long long。

---

六、图论建模基础

图论题先不要急着写最短路，先完成建模。

常见元素对应关系

题目语言	图论语言
城市、牧场、哨所、点	点 / 顶点
道路、通信线路、转账关系	边
路程、费用、时间、手续费	边权
从 A 到 B 的最小代价	最短路
所有人都收到消息的时间	从起点到最远点的最短路
选择一个集合点使总距离最小	枚举终点 + 最短路距离和

---

七、Floyd：多源最短路

适用场景

• 点数较小。
• 需要任意两点之间的最短路。
• 典型复杂度：O(n^3)。

核心状态

d[i][j]：当前已知从 i 到 j 的最短距离。

初始化

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        d[i][j] = INF;
    }
    d[i][i] = 0;
}

读边：

d[u][v] = min(d[u][v], w);
d[v][u] = min(d[v][u], w); // 无向图

转移

for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}

记忆方式

k 表示“允许经过的中转点”。

从 i 到 j，是否可以通过 k 变得更短？

---

八、Dijkstra：单源最短路

适用场景

• 边权非负。
• 从一个起点到其他点的最短距离。
• 点边较多时，优先用邻接表 + 优先队列。

朴素 Dijkstra 思路

1. dist[s] = 0，其他点为无穷大。
2. 每次选一个没有确定、且 dist 最小的点 u。
3. 用 u 去更新它能到达的点。

模板

for (int i = 1; i <= n; i++) dist[i] = INF;
dist[s] = 0;

for (int round = 1; round <= n; round++) {
    int u = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i] && (u == 0 || dist[i] < dist[u])) {
            u = i;
        }
    }

    if (u == 0 || dist[u] == INF) break;
    vis[u] = true;

    for (auto e : g[u]) {
        int v = e.to, w = e.w;
        dist[v] = min(dist[v], dist[u] + w);
    }
}

注意事项

• Dijkstra 不能处理负权边。
• 无向图要加两条边。
• 有重边时，邻接矩阵要取 min；邻接表可以直接都存。
• 如果终点距离仍是 INF，说明不可达。

---

九、最短路题型总结

1. 两点之间的最短路径

问题：给点坐标和可连边，求 s 到 t 的最短距离。

做法：

1. 先根据坐标计算直接相连两点的欧几里得距离。
2. 建图。
3. 用 Floyd 或 Dijkstra 求最短路。
4. 按要求保留小数。

距离公式：

double dis = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));

---

2. 城市路 / 热浪

问题：给无向带权图，求起点到终点的最短距离。

标准 Dijkstra。

输出：

• 可达：输出 dist[t]
• 不可达：按题意输出 -1 或 No path

---

3. 信使

问题：从 1 号点发消息，问所有点收到消息的最短总时间。

本质：

从 1 到所有点的最短路中，最大的那个距离。

做法：

Dijkstra(1);
ans = max(dist[i]);

如果存在 dist[i] == INF，输出 -1。

---

4. 香甜的黄油

问题：选择一个牧场放糖，使所有奶牛到它的距离总和最小。

做法一：Floyd

• 点数较小时，可以求任意两点最短路。
• 然后枚举糖放在哪个牧场。

for (int place = 1; place <= P; place++) {
    long long sum = 0;
    for (每头牛 cow) {
        sum += d[cow所在牧场][place];
    }
    ans = min(ans, sum);
}

做法二：多次 Dijkstra

• 点数较大、边较少时，从每个候选牧场跑一次 Dijkstra。

复习重点：

• 不是求某一头牛的最短路，而是求所有牛距离之和。
• 一个牧场可能有多头牛，可以用 cnt[pos] 统计牛的数量。

---

5. 最小花费

转账手续费题不是简单加法最短路。

如果一条边手续费为 z%，到账比例是：

rate = (100 - z) / 100.0;

经过多条边，总到账比例是乘法：

总比例 = rate1 * rate2 * rate3 * ...

为了让起点准备的钱最少，就要让总到账比例最大。

最终答案：

answer = 100.0 / bestRate;

这类题可以看成“最大乘积路径”。

转移：

if (prob[v] < prob[u] * rate) {
    prob[v] = prob[u] * rate;
}

---

十、邻接矩阵 vs 邻接表

存图方式	适合情况	优点	缺点
邻接矩阵 d[n][n]	点少、边多、Floyd	查询两点边权方便	空间大
邻接表 vector<Edge> g[n]	点多、边少、Dijkstra	节省空间	查询两点是否有边不方便

选择建议

• n <= 500 且需要任意两点最短路：可以考虑 Floyd。
• n 上千、上万，边不算特别密：优先 Dijkstra + 邻接表。
• 题目有重边：读入时要保留更短的边，或者邻接表全部加入也可以。

---

十一、常见错误清单

1. INF 不够大

如果边权和路径长度可能很大，使用：

const long long INF = 4e18;

不要直接用 INT_MAX 后再相加，否则可能溢出。

2. 忘记初始化自己到自己为 0

Floyd 和邻接矩阵 Dijkstra 都需要：

d[i][i] = 0;

3. 无向图只加了一条边

无向图必须：

g[u].push_back({v, w});
g[v].push_back({u, w});

4. 重边没有取最小值

d[u][v] = min(d[u][v], w);

5. Dijkstra 没有判断不可达

如果当前选出的点距离是 INF，说明剩下点都不可达，可以停止。

6. 小数输出格式不对

例如保留两位：

printf("%.2lf", ans);

保留八位：

printf("%.8lf", ans);

---

十二、课堂速记模板

Floyd

for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}

朴素 Dijkstra

for (int i = 1; i <= n; i++) dist[i] = INF;
dist[s] = 0;

for (int round = 1; round <= n; round++) {
    int u = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i] && (u == 0 || dist[i] < dist[u])) u = i;
    }
    if (u == 0 || dist[u] == INF) break;
    vis[u] = true;

    for (auto e : g[u]) {
        dist[e.to] = min(dist[e.to], dist[u] + e.w);
    }
}

方向数组

int dx[8] = {-1,-1,-1,0,0,1,1,1};
int dy[8] = {-1,0,1,-1,1,-1,0,1};

资源排队模拟

start = max(arrive, resourceFree);
finish = start + cost;
resourceFree = finish;

---

十三、复习路线建议

1. 先复习基础模拟：时间转换、评分、扫雷。
2. 再复习排序贪心：气球充气，理解排序后配对。
3. 接着复习图论建模：点、边、边权、起点终点。
4. 熟练背出 Floyd 和 Dijkstra 的核心循环。
5. 最后做最短路变形题：信使、香甜的黄油、最小花费。

---

十四、做题前 30 秒检查

• [ ] 这是模拟、贪心还是图论？
• [ ] 数据范围允许 O(n^3) 吗？
• [ ] 图是有向还是无向？
• [ ] 是否有重边？
• [ ] 是否可能不可达？
• [ ] 边权是整数加法，还是比例乘法？
• [ ] 答案需要整数、小数，还是保留指定位数？
• [ ] 是否需要 long long？

---

一句话总结：

模拟题靠流程清晰，贪心题靠排序后的理由，最短路题靠建模准确。先看数据范围选算法，再写模板，最后检查边界与输出格式。