在其他论坛看到一道算法题，似乎有点思路但是又想不太清楚，各位能解吗？

[shyrock]

题目描述 光明幼儿园的老师非常注意孩子的卫生，他们要给宝宝们常洗晒衣服。幼儿园的李阿姨担负这个重要任务。她洗完衣服后，就要将衣服弄干。衣服在自然条件下用 1 的时间可以晒干到 A 点湿度。但有时天气很不好，无法晾干，幼儿园买了 1 台烘干机。为了节省能源，使用烘干机可以让你用 1 的时间使 1 件衣服除开自然晒干的 A 点湿度外，还可以烘干 B 点湿度，但在 1 个时间内只能给 1 件衣服使用。

N 件的衣服因为种种原因而需要不一样湿，现在给出每件衣服的湿度，要你求出弄干所有衣服的最少时间（湿度为 0 为干）。

输入格式 第一行 N ，A ，B ；接下来 N 行，每行一个数，表示衣服的湿度（ 1<=湿度，A,B<=500000,1<=N<=500000 ）。

输出格式 一行，最少时间。

[learningman]

简单贪心即可，每次找出当前湿度最大的。
优先队列维护

[sillydaddy]

用图形化的想象容易想明白：
可以想象一个柱状图，每个柱子的高度参差不齐，代表湿度。
自然烘干作用下，代表所有的柱子，以相同的速度（ A ）下降，代表自然风干的速度；
烘干机，可以想象成在所有柱子的最高（接触）点，不断消磨柱子的高度，消磨的总面积速度是固定的（ B ），代表烘干的速度；

这样的话，最少时间，应该可以计算出来，我不知道具体是多少，应该可以简单列一个等式：
比如在高度 x 的位置，所有衣服恰好风干，花费了时间 t ，这时有等式：
x = N*t
所有柱子在 x 位置以上的面积和，等于 B*t 。

[sillydaddy]

写错了，第一个等式是 x=A*t

[xupefei]

烘干机能开半小时的话就是贪心算法，必须开整数小时的话就是把湿度取反后动态规划。

[samuel]

看题意估计时间是不可以取小数的，直接用优先队列来维护衣服的湿度变化，就是时间计算和状态更新上有点小 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

[kimera]

@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 小时

不知道这么理解有没有问题

[kimera]

java 实现了一个，写的有点乱 https://t.hk.uy/aKT9

[kimera]

@kimera
方案二
先把 17 烘干 1 个小时，此时 17 变成了 2,13 变成了 7
把 7 烘干一小时，都烘干了
总共用时 2 小时

算岔劈了 好尴尬

[zoyao]

```
/**
* @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;
}
```

[zoyao]

复杂度应该是 O(N)，v2ex 不支持 markdown 呀

[aguesuka]

什么论坛? 想看它们的答案

[MoYi123]

二分答案 O(n log max(a,b)),
用堆模拟会被特殊数据卡到 O(n*max(a,b))的.