有基础班_第四课_贪心（一）
题目 T46721.【模拟枚举】区间内素数个数 T46722.【模拟枚举】单词次数 T46741.【贪心算法(一)】书架 T46742.【贪心算法(一)】三角形的最大周长 T46743.【贪心算法(一)】打折糖果 T46744.【贪心算法(一)】接水问题
T46721.【模拟枚举】区间内素数个数
题目大意
给定两个整数 l 和 r，求在区间 [l, r]（包含 l 和 r）内有多少个素数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
题目要求统计区间内的素数个数。素数的定义是大于1的正整数，除了1和自身外没有其他因数。我们需要判断区间中每个数是否是素数，并统计素数的数量。
由于区间最大可以到 2 * 10^6，若直接对每个数逐个判断是否为素数，会导致性能瓶颈。因此，需要使用高效的素数筛法（如埃氏筛法）进行预处理。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
1. 利用埃氏筛法预处理出 1~r 内的素数标记：
* 定义一个数组 prime[]，其中 prime[i] == 0 表示 i 是素数，prime[i] == 1 表示 i 不是素数。
* 从 i=2 开始，若 prime[i]==0，则将 i 的倍数标记为非素数。
2. 遍历 [l, r] 区间，统计 prime[i]==0 的数量。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度解析
* 埃氏筛法预处理素数：O(n log log n)，其中 n = r
* 遍历 [l, r] 区间统计素数数量：O(r - l + 1)
* 总体时间复杂度为 O(n log log n)，在 r ≤ 2×10^6 的数据范围内可以通过。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
T46722.【模拟枚举】单词次数
题目大意
给定若干个英文单词，统计每个单词出现的次数，并按照字典序从小到大输出每个单词及其出现次数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
这道题是典型的“统计频次”问题，属于模拟与枚举的范畴。输入不大，重点是正确地：
1. 统计每个单词出现的次数；
2. 按照字典序排序后输出结果。
C++中可以使用 map<string, int> 容器，天然支持自动按 key（即单词）升序排序，适合本题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
1. 使用 map<string, int> 来存储单词和它出现的次数。
2. 逐个读入单词并累加到 map 中。
3. 遍历 map（会按 key 自动排序）并输出结果。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度解析
* 输入读取：O(n)
* map 插入 n 个单词：每次插入 O(log n)，总共 O(n log n)
* 输出排序后的 map：O(n)
总时间复杂度为 O(n log n)，完全可接受（n 最多为 99）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
样例说明
输入：
输出：
排序依据为字典序：am < love < so < we < you。
T46741.【贪心算法(一)】书架
题目大意
有一堆奶牛，每头奶牛有一个高度，要用最少数量的奶牛叠起来，使它们的总高度不低于书架的高度 b，输出所需最少奶牛数量。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 给定 n 头奶牛的身高，每头奶牛高度为 h_i；
* 奶牛总高度为 s，一定能满足达到书架高度 b；
* 求使用最少的奶牛，使得它们总高度 ≥ b。
目标是最小化奶牛数量，这正是贪心算法的典型应用场景。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
使用贪心算法：
1. 把所有奶牛身高从高到低排序；
2. 从高往低累加高度，直到总高度 ≥ b；
3. 此时所用的奶牛数就是答案。
为什么贪心是正确的？
* 身高越高的奶牛越能快速“凑高度”，以最少个数达到目标。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度解析
* 排序：O(n log n)
* 遍历查找满足条件的最小数量：O(n)
总时间复杂度为 O(n log n)，可以接受（n ≤ 20000）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
样例说明
输入：
排序后为：19, 18, 13, 11
从前往后选：
* 19 → 总高 19
* +18 → 总高 37
* +13 → 总高 50 ≥ 40
用了 3 头奶牛，输出为 3。
T46742.【贪心算法(一)】三角形的最大周长
题目大意
给定一个包含 n 个整数的数组，求这 n 个数中任取三个，能组成三角形（面积不为 0）的最大周长。如果没有满足条件的三角形，输出 0。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
根据三角形不等式，任意三角形三边满足：
为了让周长尽可能大，应该选择尽可能大的三条边。只要找到满足三角形不等式的三条边，其周长就是一个合法答案。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
使用 贪心算法：
1. 将数组按降序排序；
2. 从大到小枚举三元组 (a[i], a[i+1], a[i+2])；
3. 如果满足 a[i+1] + a[i+2] > a[i]，说明这三条边可以组成三角形；
4. 因为是从大到小遍历的，第一个满足条件的一定是最大周长。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度解析
* 排序：O(n log n)
* 遍历最多 n 次：O(n)
总体复杂度：O(n log n)，完全能接受（n ≤ 100）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
样例说明
输入：
排序后为：58 35 13 12 9 1
从前往后找三条边：
* 58 35 13 → 13 + 35 = 48 ≤ 58 ❌
* 35 13 12 → 13 + 12 = 25 ≤ 35 ❌
* 13 12 9 → 12 + 9 = 21 > 13 ✅
周长 = 13 + 12 + 9 = 34
T46743.【贪心算法(一)】打折糖果
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目大意
商店打折促销规则为：
* 每买两个糖果，送一个糖果，送的糖果价格 ≤ 这两个中较小的价格。
* 给出所有糖果的价格，问最少要花多少钱，才能把所有糖果都买下来。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 想花最少的钱，应该：
优先把贵的糖果作为“要付钱的”，让便宜的作为“免费糖果”。
* 所以应该从贵到便宜排序糖果价格，然后每买两个，跳过一个（送的那个）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
1. 将所有糖果价格从大到小排序；
2. 每三个糖果一组，取前两个加到总价，跳过第三个（作为赠品）；
3. 对剩下不足三个的糖果，直接加到总价；
4. 输出总价即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度解析
* 排序：O(n log n)
* 遍历加和：O(n)
总体复杂度：O(n log n)，完全可以接受（n ≤ 100）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
样例说明
输入 1：
排序后：9 7 6 5 2 2
* 买 9 + 7，送 6
* 买 5 + 2，送 2
总花费 = 9 + 7 + 5 + 2 = 23
输入 2：
排序后：10 9 5 2 1
* 买 10 + 9，送 5
* 剩下 2 + 1，全都要买
总花费 = 10 + 9 + 2 + 1 = 22
T46744.【贪心算法(一)】接水问题
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目大意
有 n 个人在一个水龙头前排队，每个人接水的时间不同，要求安排他们的接水顺序，使 所有人的平均等待时间最小。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 假设当前人接水的时间为 T_i，则后面所有人的等待时间都会增加 T_i。
* 因此，让接水时间短的人先接水，可以最小化总等待时间。
* 这是一个经典的贪心问题：按照接水时间从小到大排序。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
1. 输入每个人的接水时间；
2. 按照接水时间从小到大排序；
3. 假设排序后每个人的接水时间是 T[1], T[2], ..., T[n]，那么：
* 第1个人等待时间是 0；
* 第2个人等待时间是 T[1]；
* 第3个人等待时间是 T[1] + T[2]；
* ...
* 公式等价于 sum += T[i] * (n - i)；
4. 最后总等待时间除以人数 n 得到平均等待时间；
5. 输出保留两位小数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度解析
* 排序：O(n log n)
* 遍历计算：O(n)
总复杂度：O(n log n)，完全可接受（n ≤ 1000）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
样例说明
输入：
排序后：
等待时间：
