【GESP】C++五级练习题 luogu-P1843 奶牛晒衣服
GESP C++ 五级练习题，二分答案和贪心思想考点应用，五级考生可以练习。题目难度⭐⭐⭐☆☆，洛谷难度等级普及/提高−。
luogu-P1843 奶牛晒衣服
题目要求
题目背景
熊大妈决定给每个牛宝宝都穿上可爱的婴儿装 。但是由于衣服很湿，为牛宝宝晒衣服就成了很不爽的事情。于是，熊大妈请你（奶牛）帮助她完成这个重任。
题目描述
一件衣服在自然条件下用一秒的时间可以晒干 $a$ 点湿度。抠门的熊大妈只买了一台烘衣机 。使用用一秒烘衣机可以让一件衣服额外烘干 $b$ 点湿度（一秒晒干 $a+b$ 湿度），但在同一时间内只能烘一件衣服。现在有 $n$ 件衣服，第 $i$ 衣服的湿度为 $w_i$（保证互不相同），要你求出弄干所有衣服的最少时间（湿度为 $0$ 为干 ）。
输入格式
第一行三个整数，分别为 $n,a,b$。
接下来 $2$ 到 $n+1$ 行，第 $i$ 行输入 $w_i$。
输出格式
一行，弄干所有衣服的最少时间。
输入输出样例 #1
输入 #1
1
2
3
4
3 2 1
1
2
3
输出 #1
1
1
说明/提示
样例解释
让机器烘第三件衣服即可一秒完成。
数据范围
$1 \le w_i,a,b,n \le 5 \times 10^5$
题目分析
这是一道典型的二分答案题目，结合了贪心思想。
1. 问题分析
我们需要求出弄干所有衣服的最少时间。
- 时间越长，衣服越容易干，满足单调性。
- 因此可以使用二分答案算法来搜索最少时间。
2. 解题思路
假设我们需要 mid 秒来晒干衣服。在这个时间内：
- 自然晒干：每件衣服都会自然减少
mid * a的湿度。 - 烘干机额外贡献：如果某件衣服在自然晒干后还没干（即 $w_i > mid \times a$），就需要使用烘干机。题目指出烘干机每秒减少 $a+b$ 湿度，相对于自然晒干，它每秒额外提供 $b$ 点湿度的消除。
- 贪心策略：计算必须使用烘干机的时间。
- 首先假设所有时间都在自然晒干，减少湿度 $mid \times a$。
- 如果某件衣服仍未干，说明剩下的湿度 $need = w_i - mid \times a$ 需要靠烘干机的额外效率来消除。
- 烘干机每秒提供 $a+b$ 的湿度消除，比自然晒干多消除 $b$。因此，每使用烘干机 1 秒，实际上是额外消除了 $b$ 点湿度。
- 需要使用烘干机的时间 $t_i = \lceil \frac{need}{b} \rceil$。代码写作
(need + b - 1) / b。
- 判定条件：统计所有衣服需要的烘干机总时间 $\sum t_i$。由于只有一台机器，如果 $\sum t_i \le mid$，说明时间
mid可行；否则不可行。
3. 复杂度分析
- 二分次数：约 $\log(\max(w_i))$ 次。
- Check函数：每次检查需要遍历 $N$ 件衣服，复杂度 $O(N)$。
- 总复杂度：$O(N \log(\max(w_i)))$。对于 $N=5 \times 10^5$，计算量在合理范围内。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <algorithm>
#include <cmath>
#include <iostream>
typedef long long ll;
ll w[500005]; // 存储每件衣服的湿度
int n, a, b; // n: 衣服数量, a: 自然晒干速度, b: 烘干机额外烘干速度
// 检查函数：判断是否能在 mid 秒内晒干所有衣服
bool check(ll mid) {
ll total_time = mid; // 剩余可用的烘干机时间，初始为 mid 秒
for (int i = 1; i <= n; i++) {
// 如果这件衣服在 mid 秒内自然晒干就能干，则不需要烘干机
if (w[i] <= mid * a) {
continue;
}
// 计算扣除自然晒干 mid*a 后，还剩下的湿度
ll need = w[i] - mid * a;
// 剪枝：如果剩下的湿度连用满 mid 秒烘干机都干不了，直接返回不可行
// 注意：这里不是必须的，但可以加速。烘干机每秒额外提供 b 点湿度消除
if (need > mid * b) {
return false;
}
// 计算需要烘干机多少秒才能消除剩余的 need 湿度
// 使用整数向上取整公式 (need + b - 1) / b
// 因为烘干机每秒额外贡献 b，加上原本的 a，总共是 a+b。
// 这里只计算额外部分需要的时间，因为自然部分 mid*a 已经统一减去了。
// 实际上，衣服 i 需要 t_i 时间烘干，mid - t_i 时间自然晒。
// 总去湿 = t_i * (a+b) + (mid - t_i) * a = t_i * b + mid * a
// 所以需要满足：t_i * b + mid * a >= w[i]
// 也就是 t_i * b >= w[i] - mid * a
// 即 t_i >= (w[i] - mid * a) / b
ll time = (need + b - 1) / b;
// 如果这件衣服需要的烘干时间超过了剩余可用时间，则 mid 秒不可行
if (time > total_time) {
return false;
}
// 扣除这件衣服占用的烘干机时间
total_time -= time;
}
return true; // 所有衣服都能在 mid 秒内干，且烘干机时间够分配
}
int main() {
std::cin >> n >> a >> b;
ll r = 0; // 二分查找的上界
for (int i = 1; i <= n; i++) {
std::cin >> w[i];
r = std::max(r, w[i]); // 最坏情况：衣服全是自然晒干，需要 max(w[i]) /
// a 时间，粗略取 max(w[i]) 即可
}
ll l = 1; // 二分查找的下界
while (l <= r) {
ll mid = l + (r - l) / 2;
if (check(mid)) {
// 如果 mid 秒可行，说明答案可能是 mid 或者更小
r = mid - 1;
} else {
// 如果 mid 秒不可行，说明需要更多时间
l = mid + 1;
}
}
std::cout << l << std::endl;
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
