有基础班_第五课_贪心（二）
2025-05-22 14:26:12
发布于：上海
58阅读
0回复
0点赞
| 题目 |
|---|
| T46746.【贪心算法(一)】最优装载问题 |
| T46747.【贪心算法(一)】粮草 |
| T46745.【贪心算法(一)】接水问题二 |
| T46748.【贪心算法(一)】骑士的工作 |
| T46775.【贪心算法(二)】分发饼干 |
| T46777.【贪心算法(二)】游玩 |
| T46776.【贪心算法(二)】活动安排 |
T46746.【贪心算法(一)】最优装载问题
题目大意
一艘海盗船的最大载重量为 C，海盗们截获了一批古董，共有 n 件，每件古董的重量为 w_i。海盗们希望在不超过最大载重的前提下，尽可能多地将古董装船。你的任务是计算最多能装多少件古董。
题意分析
本题是典型的背包问题的贪心变形。我们不关注物品的总价值，只关心装得下尽量多的物品。由于没有价值限制，因此我们优先选择重量小的物品装入，从而可以装得更多。
解题思路
采用贪心策略：
- 将所有古董按重量从小到大排序；
- 然后按顺序依次尝试将古董装入船中；
- 如果当前古董能装入（累计重量未超标），则继续；
- 一旦不能装入，说明后面的更重物品也不能装，直接停止。
这是典型的“局部最优 => 全局最优”的贪心场景。
时间复杂度解析
- 排序耗时
O(n log n) - 遍历一次
O(n) - 总时间复杂度为
O(n log n)，在n ≤ 1000的范围内运行良好。
代码演示
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int c, n;
int a[1010];
cin >> c >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
// 将古董重量从小到大排序
sort(a + 1, a + 1 + n);
int weight = 0; // 当前总重量
int cnt = 0; // 已装入古董数量
for(int i = 1; i <= n; i++) {
if(weight + a[i] <= c) {
weight += a[i];
cnt++;
} else {
break; // 当前古董装不下了，结束
}
}
cout << cnt << endl;
return 0;
}
T46747.【贪心算法(一)】粮草
题目大意
有若干农户，每人给出了一种价格和能提供的最大粮草量。商会需要采购总量为 n 的粮草。
目标是从这些农户中购买足够数量的粮草，使总花费最小。
题意分析
- 每个农户提供
(单价, 数量)的信息。 - 商会可以从任意农户购买任意量（不超过其最大值）。
- 要求商会总共采购到 不少于 n 单位 的粮草。
- 输出最少的总采购花费。
解题思路
这是典型的贪心策略问题，目标是用最少的钱买到足够的粮草。
贪心策略：优先从单价最低的农户那里购买粮草。
步骤如下：
- 读取所有农户信息（单价、数量）。
- 按照单价
p_i从小到大排序。 - 从价格最便宜的农户开始购买粮草：
- 如果当前农户能满足所有剩余需求，就只买需要的部分。
- 否则把该农户所有粮草买完，然后继续从下一个便宜的农户买。
时间复杂度解析
- 排序：
O(m log m)，其中m是农户数量。 - 遍历农户：
O(m) - 总体复杂度：
O(m log m)，在m ≤ 5000的范围内表现良好。
代码演示
#include<iostream>
#include<algorithm>
using namespace std;
struct Farmer {
int price; // 单价
int amount; // 能提供的粮草量
} a[5010];
// 比较函数：按单价升序排列
bool cmp(Farmer x, Farmer y) {
return x.price < y.price;
}
int main() {
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; i++) {
cin >> a[i].price >> a[i].amount;
}
// 贪心排序：单价从小到大
sort(a + 1, a + 1 + m, cmp);
int bought = 0; // 当前已买粮草数量
int totalCost = 0; // 当前总花费
for(int i = 1; i <= m; i++) {
if(bought + a[i].amount < n) {
// 当前农户的粮草全部买下也不够
totalCost += a[i].price * a[i].amount;
bought += a[i].amount;
} else {
// 只需买部分就够了
totalCost += a[i].price * (n - bought);
break; // 已满足需求
}
}
cout << totalCost << endl;
return 0;
}
T46745.【贪心算法(一)】接水问题二
一、题目大意
给定 n 个人，每个人接水所需时间为 T_i，只能一个人一个人依次接水。现在要安排这 n 个人的接水顺序，使得 所有人平均等待时间最小。输出该顺序中每个人的原始编号，并输出最小平均等待时间（保留两位小数）。
二、题意分析
- 每个人的等待时间 = 前面所有人接水时间之和。
- 总等待时间 = 所有人的等待时间加总。
- 平均等待时间 = 总等待时间 /
n
要想平均等待时间最小，就要让耗时短的人排在前面，减少其接水时间对后续人员的影响。
三、解题思路
贪心策略：
我们从另一个角度看问题：
第 i 个人接水的时间是 a[i]，他会让后面 n - i 个人都等待 a[i] 时间。
因此：
- 每个人的接水时间对总等待时间的贡献是：
a[i] * (n - i) - 要让总等待时间最小，就让
a[i]越小的人越早排。
实现步骤：
- 将每个人的接水时间和原始编号一起读入；
- 按接水时间升序排序；
- 遍历每个人，累加其对总等待时间的贡献；
- 输出排序后的编号序列；
- 计算并输出平均等待时间。
四、时间复杂度分析
- 排序时间复杂度：
O(n log n) - 遍历计算总等待时间：
O(n) - 总体复杂度为：
O(n log n)，在n <= 1000范围内可以轻松通过。
五、代码演示
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
struct Person {
int id; // 原始编号
int time; // 接水时间
} a[1010];
// 按接水时间升序排序
bool cmp(Person x, Person y) {
return x.time < y.time;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].time;
a[i].id = i;
}
sort(a + 1, a + 1 + n, cmp);
double totalWait = 0;
for (int i = 1; i <= n; i++) {
// 第i个人接水时，后面n - i人都要等待a[i].time秒
totalWait += a[i].time * (n - i);
}
for (int i = 1; i <= n; i++) {
cout << a[i].id;
if (i < n) cout << " ";
else cout << endl;
}
printf("%.2f\n", totalWait / n);
return 0;
}
T46748.【贪心算法(一)】骑士的工作
题目大意
一条恶龙有 n 个头，每个头有一个大小。你需要找来一些骑士来砍掉这些头。共有 m 位骑士，每个骑士只能砍掉一个大小不超过他能力值的头，且出战需要支付与能力值相同的金币数。你需要选择若干骑士，让他们砍掉所有龙头，且总花费最少。如果无法砍完所有龙头，输出 "you died!"。
题意分析
- 每个龙头只能被一个骑士砍掉；
- 每位骑士只能砍一个头，不能重复使用；
- 骑士的能力值即为费用，能力越强，花费越高；
- 目标是完成全部龙头的砍杀任务，并使总金币花费最少。
解题思路
我们采用贪心算法来解决这个问题。
- 将所有龙头按大小升序排列；
- 将所有骑士按能力值升序排列；
- 对于每一个龙头，从前往后找能力值刚好或刚好大于它的最便宜的骑士；
- 找到合适的骑士后安排出战，记录花费，并同时跳过该骑士；
- 如果某个龙头找不到骑士能砍掉，直接输出
"you died!"。
这种贪心策略是可行的，因为：
- 较小的龙头优先被能力值低的骑士砍掉，节省费用；
- 强力骑士保留给更大的龙头使用。
时间复杂度解析
- 排序耗时
O(n log n + m log m) - 遍历两个数组进行匹配
O(n + m) - 总时间复杂度为
O(n log n)，在n, m ≤ 20000的范围内运行良好。
代码演示
#include <iostream>
#include <algorithm>
using namespace std;
int head[20010]; // 龙头大小数组
int knight[20010]; // 骑士能力值数组
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> head[i];
for (int i = 1; i <= m; i++) cin >> knight[i];
sort(head + 1, head + 1 + n); // 按龙头大小升序排列
sort(knight + 1, knight + 1 + m); // 按骑士能力升序排列
int i = 1, j = 1, totalCost = 0;
while (i <= n && j <= m) {
if (knight[j] >= head[i]) {
totalCost += knight[j];
i++; j++;
} else {
j++;
}
}
if (i > n) cout << totalCost << endl;
else cout << "you died!" << endl;
return 0;
}
T46775.【贪心算法(二)】分发饼干
题目大意
有 n 盒大小不同的饼干，要分给 m 个孩子。每个孩子有一个“期望的饼干大小”，只有当饼干大小 ≥ 他的期望值时，他才会满意。每个孩子最多只能得到一盒饼干，问最多有多少个孩子可以获得满足。
题意分析
- 每个孩子最多只能分到一盒饼干；
- 一盒饼干也只能分给一个孩子；
- 饼干的大小必须 大于等于 孩子的期望值才能使他满意；
- 要使尽可能多的孩子满意。
解题思路
采用 贪心策略：
- 将所有饼干大小从小到大排序；
- 将所有孩子的期望值从小到大排序；
- 用双指针
i和j分别指向当前考虑的饼干和孩子：- 如果当前饼干可以满足当前孩子，则分配它，两个指针都后移；
- 否则说明饼干太小，只能尝试下一块更大的饼干；
- 重复直到饼干或孩子遍历完。
贪心的核心思路是：
小的饼干优先满足小的需求，避免“大饼干喂小孩”造成浪费。
时间复杂度解析
- 排序饼干数组：
O(n log n) - 排序孩子需求数组：
O(m log m) - 双指针遍历：
O(n + m) - 总体时间复杂度为
O(n log n + m log m)，在n, m ≤ 10000的范围内表现良好。
代码演示
#include <algorithm>
#include <iostream>
using namespace std;
// g[] 存储每盒饼干的大小，c[] 存储每个孩子的需求
int g[10010], c[10010];
int main() {
int n, m;
cin >> n >> m; // 输入饼干数量和孩子数量
// 输入每盒饼干的大小
for (int i = 1; i <= n; i++) {
cin >> g[i];
}
// 输入每个孩子的需求值
for (int i = 1; i <= m; i++) {
cin >> c[i];
}
// 按照从小到大排序饼干和孩子需求
sort(g + 1, g + 1 + n); // g[1]~g[n]
sort(c + 1, c + 1 + m); // c[1]~c[m]
int i = 1, j = 1; // i：当前饼干下标，j：当前孩子下标
int cnt = 0; // cnt：成功被满足的孩子数
// 当饼干和孩子都还有未处理的情况时继续
while (i <= n && j <= m) {
if (g[i] >= c[j]) {
// 当前饼干可以满足当前孩子
cnt++; // 满意孩子数+1
i++; // 指向下一盒饼干
j++; // 指向下一个孩子
} else {
// 当前饼干太小，无法满足这个孩子
i++; // 换更大的饼干继续尝试
}
}
// 输出最终可以满足的孩子数
cout << cnt << endl;
return 0;
}
T46777.【贪心算法(二)】游玩
题目大意
有 n 个人出海游玩，每艘船最多能承载两个人，且总重量不能超过 m。每个人有一个固定的体重。现在希望用最少数量的船把所有人都送出去，求最小的船只数量。
题意分析
- 每艘船最多坐两人；
- 两人的总重量不能超过
m； - 每人必须上船，不能遗漏；
- 要求使用最少数量的船。
解题思路
采用 贪心策略 + 双指针：
- 将所有人的体重从小到大排序；
- 用两个指针
i（最轻的人）和j（最重的人）； - 每次尝试将最轻和最重的人配对上船：
- 如果他们的体重之和不超过最大载重
m，则配对成功，i++,j--； - 否则，只能让重的人单独上船，
j--；
- 如果他们的体重之和不超过最大载重
- 每次操作代表一艘船，计数器
sum++； - 循环直到所有人都分配完。
贪心思想是：
用最重的人尽量去“搭配”最轻的人，节省船只数量。
时间复杂度解析
- 排序体重数组：
O(n log n) - 双指针遍历：
O(n) - 总体时间复杂度：
O(n log n)，对于n ≤ 1000表现良好。
代码演示
#include <algorithm>
#include <iostream>
using namespace std;
int arr[1010];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
sort(arr + 1, arr + 1 + n); // 升序排列体重
int i = 1, j = n;
int sum = 0; // 船只数量
while (i <= j) {
if (arr[i] + arr[j] <= m) {
// 最轻和最重的可以同船
i++;
j--;
} else {
// 最重的只能单独坐
j--;
}
sum++; // 每次循环都用掉一艘船
}
cout << sum << endl;
return 0;
}
T46776.【贪心算法(二)】活动安排
题目大意
给定 n 个活动，每个活动有一个开始时间 s 和结束时间 e。如果一个活动的开始时间大于等于另一个活动的结束时间，那么可以连续参加这两个活动。
问：最多可以参加多少个互不重叠的活动？
题意分析
- 每个活动只能选择一次；
- 活动时间不能重叠；
- 可以选的活动顺序不固定；
- 目标是选择尽可能多的活动。
解题思路
采用 贪心策略（按照结束时间排序）：
- 将所有活动按照结束时间升序排序；
- 每次选择当前结束时间最早，且不与已选活动冲突（开始时间 ≥ 上一个活动的结束时间）的活动；
- 更新当前的时间
now = 当前活动的结束时间，统计可选的活动数量。
贪心的核心思想是：
优先安排结束早的活动，为后续活动留出更多空间，最大化可选数量。
时间复杂度解析
- 排序活动数组：
O(n log n) - 遍历判断可选活动：
O(n) - 总体时间复杂度为
O(n log n)，在n ≤ 1000范围内可以高效运行。
代码演示
#include <algorithm>
#include <iostream>
using namespace std;
struct Activity {
int start, end;
} a[1010];
// 按结束时间升序排序
bool cmp(Activity x, Activity y) {
return x.end < y.end;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].start >> a[i].end;
}
sort(a + 1, a + 1 + n, cmp); // 按结束时间排序
int now = 0, cnt = 0; // now：当前结束时间，cnt：已选活动数
for (int i = 1; i <= n; i++) {
if (a[i].start >= now) {
cnt++;
now = a[i].end; // 更新当前时间
}
}
cout << cnt << endl;
return 0;
}
有帮助，赞一个