贪心法
课上练习
知识总结
贪心法-知识总结
贪心法-知识总结 核心思想 每次都选最好的！
适用问题 可通过局部最优解推出全局最优解的问题： 求“最"值或状态的问题 需要多步操作的问题
解题思路 识别问题类型 归纳贪心公式，即每一步的贪心方法 通过反例确认公式正确性
贪心案例 选择排序 冒泡排序 插入排序
️课后作业
☝️总结作业
总结作业非常重要，请务必认真完成✔️
- 贪心法的核心思想是什么？
- 贪心法一般用来解什么样的问题？
- 贪心法的一般解题思路是什么？
✌️编程作业
考试只有一次提交机会，请务必本地检查正确后再提交❇️
👌编程作业标准答案
请在AC后或者思考15分钟没有进展后查看，不可抄代码❇️
L2143题解+参考代码
L2143题解+参考代码 题目链接 排队接水：L2143
题解 为了使 n 个人的平均等待时间最小，我们需要让接水时间短的人先接水。这样每个人的等待时间都是前面所有人的接水时间之和，最短接水时间的人排在前面可以有效减少后面人的等待时间。
算法步骤 读取输入：读取人数 n 和每个人的接水时间列表。 使用选择排序对接水时间进行排序： 在每一轮中找到当前未排序部分中接水时间最短的人，并将其交换到当前未排序部分的最前面。 同时记录排序后的编号。 计算总等待时间： 初始化总等待时间 totalWaitTime 为 0。 遍历排好序的接水时间，累加当前人的等待时间到 totalWaitTime 中。 计算平均等待时间：使用总等待时间除以 n 计算平均等待时间。 输出结果：输出排序后的编号和计算的平均等待时间。 示例代码 这里是使用 C++ 实现的示例代码：
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 // 读取输入
6 int n;
7 cin >> n;
8 int times[1000];
9 int indices[1000];
10 for (int i = 0; i < n; ++i) {
11 cin >> times[i];
12 indices[i] = i + 1;
13 }
14
15 // 使用选择排序对接水时间进行排序，同时记录编号
16 for (int i = 0; i < n - 1; ++i) {
17 int minIndex = i;
18 for (int j = i + 1; j < n; ++j) {
19 if (times[j] < times[minIndex]) {
20 minIndex = j;
21 }
22 }
23 // 交换接水时间
24 swap(times[i], times[minIndex]);
25 // 交换对应的编号
26 swap(indices[i], indices[minIndex]);
27 }
28
29 // 计算总等待时间和排序后的编号
30 int totalWaitTime = 0;
31 int currentTime = 0;
32 for (int i = 0; i < n; ++i) {
33 if (i > 0) {
34 currentTime += times[i-1];
35 totalWaitTime += currentTime;
36 }
37 }
38
39 // 计算平均等待时间
40 double averageWaitTime = static_cast<double>(totalWaitTime) / n;
41
42 // 输出排序后的编号
43 for (int i = 0; i < n; ++i) {
44 cout << indices[i] << (i == n - 1 ? '\n' : ' ');
45 }
46
47 // 输出平均等待时间
48 cout << fixed << setprecision(2) << averageWaitTime << endl;
49
50 return 0;
51}L2144题解+参考代码
L2144题解+参考代码 题目链接 均分纸牌：L2144
题解 要使得 n 堆纸牌每堆上的纸牌数都相等，我们可以通过移动纸牌使得每堆纸牌都达到目标数量。目标数量是所有纸牌的总数除以 n。
算法步骤 读取输入：读取纸牌堆数 n 和每堆纸牌的初始数量。 计算目标数量：计算每堆纸牌需要达到的目标数量，目标数量为总纸牌数除以 n。 初始化移动次数：定义一个变量 moves 用于记录总的移动次数。 移动纸牌： 从左到右遍历每堆纸牌，如果当前堆纸牌数量大于目标数量，将多余的纸牌移动到右边的堆。 如果当前堆纸牌数量小于目标数量，从右边的堆补足差额。 每次移动纸牌时增加 moves。 输出结果：输出总的移动次数。 示例代码 这里是使用 C++ 实现的示例代码：
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 // 读取输入
6 int n;
7 cin >> n;
8 int piles[100];
9 int total = 0;
10 for (int i = 0; i < n; ++i) {
11 cin >> piles[i];
12 total += piles[i];
13 }
14
15 // 计算目标数量
16 int target = total / n;
17 int moves = 0;
18
19 // 移动纸牌
20 for (int i = 0; i < n - 1; ++i) {
21 int diff = piles[i] - target;
22 piles[i] -= diff;
23 piles[i + 1] += diff;
24 if (diff != 0) {
25 moves++;
26 }
27 }
28
29 // 输出结果
30 cout << moves << endl;
31
32 return 0;
33}