这是一个创建于 999 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目描述 光明幼儿园的老师非常注意孩子的卫生，他们要给宝宝们常洗晒衣服。幼儿园的李阿姨担负这个重要任务。她洗完衣服后，就要将衣服弄干。衣服在自然条件下用 1 的时间可以晒干到 A 点湿度。但有时天气很不好，无法晾干，幼儿园买了 1 台烘干机。为了节省能源，使用烘干机可以让你用 1 的时间使 1 件衣服除开自然晒干的 A 点湿度外，还可以烘干 B 点湿度，但在 1 个时间内只能给 1 件衣服使用。
N 件的衣服因为种种原因而需要不一样湿，现在给出每件衣服的湿度，要你求出弄干所有衣服的最少时间（湿度为 0 为干）。
输入格式 第一行 N ，A ，B ；接下来 N 行，每行一个数，表示衣服的湿度（ 1<=湿度，A,B<=500000,1<=N<=500000 ）。
输出格式 一行，最少时间。
 |
1
learningman 2022-02-10 19:47:16 +08:00  1
简单贪心即可，每次找出当前湿度最大的。
优先队列维护 |
 |
2
sillydaddy 2022-02-10 20:40:44 +08:00 1
用图形化的想象容易想明白：
可以想象一个柱状图，每个柱子的高度参差不齐，代表湿度。 自然烘干作用下，代表所有的柱子，以相同的速度（ A ）下降，代表自然风干的速度； 烘干机，可以想象成在所有柱子的最高（接触）点，不断消磨柱子的高度，消磨的总面积速度是固定的（ B ），代表烘干的速度； 这样的话，最少时间，应该可以计算出来，我不知道具体是多少，应该可以简单列一个等式： 比如在高度 x 的位置，所有衣服恰好风干，花费了时间 t ，这时有等式： x = N*t 所有柱子在 x 位置以上的面积和，等于 B*t 。 |
|
3
sillydaddy 2022-02-10 20:53:50 +08:00
写错了，第一个等式是 x=A*t
|
 |
4
xupefei 2022-02-10 23:09:15 +08:00 via iPhone
烘干机能开半小时的话就是贪心算法，必须开整数小时的话就是把湿度取反后动态规划。
|
 |
5
samuel 2022-02-10 23:42:04 +08:00
看题意估计时间是不可以取小数的，直接用优先队列来维护衣服的湿度变化，就是时间计算和状态更新上有点小 trick ，关键点是不要 每次迭代都更新全部衣服的湿度，那会带来 N^2 的复杂度
差不多是这个样子，感觉复杂度应该是 O(N)，因为每次都尽可能的把当前衣服烘干，所以一衣服最多能有机会被烘两次 from queue import PriorityQueue import math def dry(N, A, B, clothes): q = PriorityQueue() for h in clothes: q.put(-h) elapsed = 0 while True: head = q.get() * -1 if elapsed * A > head: break delta = max(int(math.floor((head - A * elapsed * 1.0) / (A+B))), 1) elapsed += delta new_head = head - delta * B q.put(-new_head) return elapsed |
 |
6
kimera 2022-02-11 12:45:32 +08:00
@learningman
方案一： - 流程描述 每次取出一件最湿的衣服，然后完全弄干，在处理下一件衣服 方案二 - 流程描述 取出一件最湿的衣服，然后部分弄干（比下一件衣服稍微干一点就可以了），然后取出，放回队列 换下一件衣服弄干 =============================== 测试数据 arr=[17,13],A=6,B=9 方案一 先把 17 完全弄干，用时 17/(9+6),向上取整，用时 2 此时 13 变成 1, 可以自然风干或烘干机，还需要 1 小时 总共用时 3 方案二 先把 17 烘干 2 个小时，此时 17 变成了 0,13 变成了 1 可以自然风干或烘干机，还需要 1 小时 总共用时 2 小时 不知道这么理解有没有问题 |
|
7
kimera 2022-02-11 12:55:21 +08:00
java 实现了一个，写的有点乱 https://t.hk.uy/aKT9
|
|
8
kimera 2022-02-11 13:07:24 +08:00
|
 |
9
zoyao 2022-02-11 15:15:27 +08:00
```
/** * @author zoyao. * @create 2022/2/11 * @param a 自然烘干每单位时间烘干湿度 * @param b 机器烘干每单位时间烘干湿度 * @param cloths 所有待烘干衣服 * @return */ public double dry(int a, int b, int[] cloths) { Arrays.sort(cloths); long total = Arrays.stream(cloths).sum(); double hourMin = cloths[cloths.length - 1]; //假设烘干时间在 cloths[i-1]至 cloths[i]之间 for (int i = 0; i < cloths.length; i++) { int cloth = cloths[i]; //只计算所有湿度大于等于 cloths[i-1]的衣服 //自然烘干:a * (cloths.length - i) * hour //机器烘干:b * hour double hour = (double) total / (a * (cloths.length - i) + b); total -= cloth; //不满足上述假设条件 if (hour > cloth || (i > 0 && hour < cloths[i - 1])) { continue; } if (hour < hourMin) { hourMin = hour; } } return hourMin; } ``` |
|
10
zoyao 2022-02-11 15:22:27 +08:00
复杂度应该是 O(N)，v2ex 不支持 markdown 呀
|
 |
11
aguesuka 2022-02-11 16:52:46 +08:00
什么论坛? 想看它们的答案
|
 |
12
MoYi123 2022-02-12 10:54:21 +08:00
二分答案 O(n log max(a,b)),
用堆模拟会被特殊数据卡到 O(n*max(a,b))的. |
Select Language