有基础班_第四课_贪心（一）
2025-05-18 16:40:55
发布于：上海
61阅读
0回复
0点赞
有基础班_第四课_贪心（一）
| 题目 |
|---|
| T46721.【模拟枚举】区间内素数个数 |
| T46722.【模拟枚举】单词次数 |
| T46741.【贪心算法(一)】书架 |
| T46742.【贪心算法(一)】三角形的最大周长 |
| T46743.【贪心算法(一)】打折糖果 |
| T46744.【贪心算法(一)】接水问题 |
T46721.【模拟枚举】区间内素数个数
题目大意
给定两个整数 l 和 r，求在区间 [l, r]（包含 l 和 r）内有多少个素数。
题意分析
题目要求统计区间内的素数个数。素数的定义是大于1的正整数，除了1和自身外没有其他因数。我们需要判断区间中每个数是否是素数，并统计素数的数量。
由于区间最大可以到 2 * 10^6，若直接对每个数逐个判断是否为素数，会导致性能瓶颈。因此，需要使用高效的素数筛法（如埃氏筛法）进行预处理。
解题思路
- 利用埃氏筛法预处理出
1~r内的素数标记：- 定义一个数组
prime[]，其中prime[i] == 0表示i是素数，prime[i] == 1表示i不是素数。 - 从
i=2开始，若prime[i]==0，则将i的倍数标记为非素数。
- 定义一个数组
- 遍历
[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的数据范围内可以通过。
代码演示
#include <iostream>
#include <cmath>
using namespace std;
int prime[2000010]; // 0 表示是素数，1 表示不是素数
int main() {
int l, r;
cin >> l >> r;
// 1 不是素数
prime[1] = 1;
// 埃氏筛法，筛选 1~r 以内的素数
for (int i = 2; i <= sqrt(r); i++) {
if (prime[i] == 0) {
for (int j = i * i; j <= r; j += i) {
prime[j] = 1;
}
}
}
// 统计区间 [l, r] 内的素数数量
int cnt = 0;
for (int i = l; i <= r; i++) {
if (prime[i] == 0) cnt++;
}
cout << cnt << endl;
return 0;
}
T46722.【模拟枚举】单词次数
题目大意
给定若干个英文单词，统计每个单词出现的次数，并按照字典序从小到大输出每个单词及其出现次数。
题意分析
这道题是典型的“统计频次”问题，属于模拟与枚举的范畴。输入不大，重点是正确地：
- 统计每个单词出现的次数；
- 按照字典序排序后输出结果。
C++中可以使用 map<string, int> 容器，天然支持自动按 key（即单词）升序排序，适合本题。
解题思路
- 使用
map<string, int>来存储单词和它出现的次数。 - 逐个读入单词并累加到 map 中。
- 遍历 map（会按 key 自动排序）并输出结果。
时间复杂度解析
- 输入读取：O(n)
- map 插入 n 个单词：每次插入 O(log n)，总共 O(n log n)
- 输出排序后的 map：O(n)
总时间复杂度为 O(n log n)，完全可接受（n 最多为 99）。
代码演示
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
int n;
cin >> n;
map<string, int> mp;
// 读取单词并统计次数
for (int i = 0; i < n; i++) {
string word;
cin >> word;
mp[word]++;
}
// 输出按字典序排序的结果
for (auto it = mp.begin(); it != mp.end(); ++it) {
cout << it->first << " " << it->second << endl;
}
return 0;
}
样例说明
输入：
8
we you we am you love so we
输出：
am 1
love 1
so 1
we 3
you 2
排序依据为字典序：am < love < so < we < you。
T46741.【贪心算法(一)】书架
题目大意
有一堆奶牛，每头奶牛有一个高度，要用最少数量的奶牛叠起来，使它们的总高度不低于书架的高度 b，输出所需最少奶牛数量。
题意分析
- 给定
n头奶牛的身高，每头奶牛高度为h_i； - 奶牛总高度为
s，一定能满足达到书架高度b； - 求使用最少的奶牛，使得它们总高度 ≥
b。
目标是最小化奶牛数量，这正是贪心算法的典型应用场景。
解题思路
使用贪心算法：
- 把所有奶牛身高从高到低排序；
- 从高往低累加高度，直到总高度 ≥
b； - 此时所用的奶牛数就是答案。
为什么贪心是正确的？
- 身高越高的奶牛越能快速“凑高度”，以最少个数达到目标。
时间复杂度解析
- 排序：O(n log n)
- 遍历查找满足条件的最小数量：O(n)
总时间复杂度为 O(n log n)，可以接受（n ≤ 20000）。
代码演示
#include <iostream>
#include <algorithm>
using namespace std;
// 自定义降序比较函数
bool cmp(int x, int y) {
return x > y;
}
int main() {
int n, b;
int a[20010]; // 奶牛身高数组
cin >> n >> b;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
// 从高到低排序
sort(a + 1, a + n + 1, cmp);
int sum = 0, cnt = 0;
for (int i = 1; i <= n; i++) {
sum += a[i];
cnt++;
if (sum >= b) break;
}
cout << cnt << endl;
return 0;
}
样例说明
输入：
4 40
18 11 13 19
排序后为：19, 18, 13, 11
从前往后选：
- 19 → 总高 19
- +18 → 总高 37
- +13 → 总高 50 ≥ 40
用了 3 头奶牛，输出为 3。
T46742.【贪心算法(一)】三角形的最大周长
题目大意
给定一个包含 n 个整数的数组，求这 n 个数中任取三个，能组成三角形（面积不为 0）的最大周长。如果没有满足条件的三角形，输出 0。
题意分析
根据三角形不等式，任意三角形三边满足：
a + b > c （其中 c 是三边中最长的）
为了让周长尽可能大，应该选择尽可能大的三条边。只要找到满足三角形不等式的三条边，其周长就是一个合法答案。
解题思路
使用 贪心算法：
- 将数组按降序排序；
- 从大到小枚举三元组
(a[i], a[i+1], a[i+2])； - 如果满足
a[i+1] + a[i+2] > a[i]，说明这三条边可以组成三角形； - 因为是从大到小遍历的，第一个满足条件的一定是最大周长。
时间复杂度解析
- 排序：O(n log n)
- 遍历最多 n 次：O(n)
总体复杂度：O(n log n)，完全能接受（n ≤ 100）
代码演示
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(int x, int y) {
return x > y;
}
int main() {
int n, a[110];
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
// 按降序排序
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n - 2; i++) {
if (a[i + 1] + a[i + 2] > a[i]) {
// 满足三角形条件，直接输出最大周长
cout << a[i] + a[i + 1] + a[i + 2] << endl;
return 0;
}
}
// 没有满足三角形不等式的三边
cout << 0 << endl;
return 0;
}
样例说明
输入：
6
12 35 58 13 1 9
排序后为：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.【贪心算法(一)】打折糖果
题目大意
商店打折促销规则为：
- 每买两个糖果，送一个糖果，送的糖果价格 ≤ 这两个中较小的价格。
- 给出所有糖果的价格，问最少要花多少钱，才能把所有糖果都买下来。
题意分析
- 想花最少的钱，应该：
优先把贵的糖果作为“要付钱的”，让便宜的作为“免费糖果”。 - 所以应该从贵到便宜排序糖果价格，然后每买两个，跳过一个（送的那个）。
解题思路
- 将所有糖果价格从大到小排序；
- 每三个糖果一组，取前两个加到总价，跳过第三个（作为赠品）；
- 对剩下不足三个的糖果，直接加到总价；
- 输出总价即可。
时间复杂度解析
- 排序：O(n log n)
- 遍历加和：O(n)
总体复杂度：O(n log n)，完全可以接受（n ≤ 100）
代码演示
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(int x, int y) {
return x > y;
}
int main() {
int n, a[110];
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
// 降序排序
sort(a + 1, a + n + 1, cmp);
int sum = 0;
for (int i = 1; i <= n; i += 3) {
sum += a[i]; // 第一个糖果
if (i + 1 <= n) {
sum += a[i + 1]; // 第二个糖果
}
// 第三个糖果 a[i+2] 不加，作为赠品
}
cout << sum << endl;
return 0;
}
样例说明
输入 1：
6
6 5 7 9 2 2
排序后：9 7 6 5 2 2
- 买 9 + 7，送 6
- 买 5 + 2，送 2
总花费 = 9 + 7 + 5 + 2 = 23
输入 2：
5
1 2 10 9 5
排序后：10 9 5 2 1
- 买 10 + 9，送 5
- 剩下 2 + 1，全都要买
总花费 = 10 + 9 + 2 + 1 = 22
T46744.【贪心算法(一)】接水问题
题目大意
有 n 个人在一个水龙头前排队，每个人接水的时间不同，要求安排他们的接水顺序，使 所有人的平均等待时间最小。
题意分析
- 假设当前人接水的时间为
T_i，则后面所有人的等待时间都会增加T_i。 - 因此，让接水时间短的人先接水，可以最小化总等待时间。
- 这是一个经典的贪心问题：按照接水时间从小到大排序。
解题思路
- 输入每个人的接水时间；
- 按照接水时间从小到大排序；
- 假设排序后每个人的接水时间是
T[1], T[2], ..., T[n]，那么：- 第1个人等待时间是 0；
- 第2个人等待时间是
T[1]； - 第3个人等待时间是
T[1] + T[2]； - ...
- 公式等价于
sum += T[i] * (n - i)；
- 最后总等待时间除以人数
n得到平均等待时间； - 输出保留两位小数。
时间复杂度解析
- 排序：O(n log n)
- 遍历计算：O(n)
总复杂度：O(n log n)，完全可接受（n ≤ 1000）
代码演示
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main() {
int n, a[1010];
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
// 贪心策略：时间短的先接水
sort(a + 1, a + n + 1);
int sum = 0;
for(int i = 1; i <= n; i++) {
sum += a[i] * (n - i); // 每个人对后面等待者的影响
}
printf("%.2f", sum / (double)n);
return 0;
}
样例说明
输入：
10
56 12 1 99 1000 234 33 55 99 812
排序后：
1 12 33 55 56 99 99 234 812 1000
等待时间：
9*1 + 8*12 + 7*33 + 6*55 + 5*56 + 4*99 + 3*99 + 2*234 + 1*812 + 0*1000
= 9 + 96 + 231 + 330 + 280 + 396 + 297 + 468 + 812 + 0 = 2919
平均等待时间 = 2919 / 10 = 291.90
这里空空如也
有帮助，赞一个