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

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

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

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

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

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

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

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

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

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

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

算岔劈了 好尴尬

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

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

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

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