当前位置：首页 > news >正文

GESP5级C++考试语法知识（贪心算法（一）课堂例题精讲）

news 2026/5/5 1:31:02

🎮《贪心王国·第一课闯关挑战》

🏴‍☠️ 第一类：海盗船系列（选最小）

🎯 第1关（基础入门）

1、题目：

容量 = 10
货物：1 2 3 4 5

👉 最多能装几件？

2、✅ 正确答案

4件（1+2+3+4=10）

3、❗ 常见错误

👉 有学生选：5 + 4 = 9（只装2件）

4、💡 学习重点

👉目标是“数量最多”，不是“体积最大”！

🎯 第2关（顺序陷阱）

1、题目：

容量 = 10
货物：8 1 9 2 7

2、❗ 坑点

👉 数据是乱序的！

3、✅ 正确思路

排序 → 1 2 7 8 9
→ 1+2+7=10 → 3件

4、❗ 常见错误

👉 不排序，直接从前往后选

5、💡 讲解一句话

👉贪心之前，很多题必须排序！

🎯 第3关（边界陷阱）

1、题目：

容量 = 10
货物：2 3 5

2、❗ 坑点

👉 刚好装满

3、❗ 常见错误

👉 写成< 10而不是<= 10

4、💡 讲解重点

👉等于也可以装！

🎯 第4关（“贪大”误区）

1、题目：

容量 = 10
货物：6 4 3 3

2、❗ 常见错误思路

👉 选最大的：6 → 剩4 → 再选4 → 2件

3、✅ 正确答案

3件（3+3+4=10）

4、💡 核心讲解

👉这题专门打脸“选最大”的错误贪心！

🎯 第5关（装不满陷阱）

1、题目：

容量 = 10
货物：6 6 6

2、✅ 正确答案

1件

3、❗ 常见错误

👉 有学生会觉得“装不满就不选”

4、💡 讲解重点

👉目标是尽量多，不是必须装满！

海盗船参考程序：

#include <iostream> #include <algorithm> using namespace std; int main() { int n, a[25]; cin >> n; for(int i = 0; i < n; i++) { cin >> a[i]; } // 从小到大排序 sort(a, a + n); int sum = 0; // 当前体积 int cnt = 0; // 装了多少件 for(int i = 0; i < n; i++) { if(sum + a[i] <= 500) { sum += a[i]; cnt++; } else { break; } } cout << cnt; }

🚰 第二类：排队接水（选最短时间）

🎯 第6关（基础）

1、题目：

3个人：3 1 2

👉 最优顺序？

2、✅ 正确答案

1 2 3

3、❗ 常见错误

👉 按输入顺序不变

4、💡 讲解重点

👉必须排序！

🎯 第7关（直觉误导）

1、题目：

时间：10 1 1

2、❗ 常见错误

👉 有学生会让“最长的先”（误以为公平）

3、✅ 正确答案

1 1 10

4、💡 讲解重点

👉贪心不是“公平”，而是“总时间最优”

🎯 第8关（重复值陷阱）

1、题目：

时间：5 5 5 5

2、❗ 坑点

👉 全一样！

3、✅ 正确结论

👉 顺序无所谓

4、💡 讲解重点

👉当数据相同时，贪心策略不唯一

🎯 第9关（计算陷阱）

1、题目：

时间：1 2 3

👉 平均等待时间？

2、❗ 常见错误

👉 只算总时间，不算等待

3、✅ 正确计算

顺序：1 2 3

等待：
1 → 0
2 → 1
3 → 1+2=3

总等待 = 4
平均 = 4 / 3

4、💡 讲解重点

👉等待时间是“前面所有人的和”！

🎯 第10关（综合大坑）

1、题目：

时间：8 3 5 1

2、❗ 常见错误流程

不排序
或排序后不会算等待

3、✅ 正确步骤

排序 → 1 3 5 8

等待：

1 → 0
3 → 1
5 → 1+3=4
8 → 1+3+5=9

4、💡 核心讲解

👉排序 + 累加 = 贪心核心套路

接水问题参考程序：

#include <iostream> #include <algorithm> using namespace std; int main() { int n; cin >> n; int t[1000]; for(int i = 0; i < n; i++) { cin >> t[i]; } sort(t, t + n); // 从小到大 long long wait = 0; long long sum = 0; for(int i = 0; i < n; i++) { sum += wait; wait += t[i]; } double avg = (double)sum / n; cout << avg; }