一 问题描述

二 算法设计

可以用二分法来求最少用的时间，关键地方是用 mid 来缩小范围。判断函数是这个问题的关键。

简单情况：如果所有的 a[i] 都小于 mid，那么肯定是可行的，都不需要用烘干机，自然风干也不会超过 mid。

如果有的 a[i] 大于 mid，怎样处理呢？

可以让所有 a[i] 大于 mid 的衣服使用烘干机，而 a[i] 不大于 mid 的衣服自然风干就可以了。

假设衣服 a[i] > mid，用了 t 时间的烘干机，剩余的时间 mid-t 选择自然风干。那么 a[i] = k*t + mid-t,t = (a[i]-mid)/(k-1)。

只需要看这些 a[i]>mid 的衣服用的烘干时间的总和有没有超过 mid，如果超过了，肯定是不满足的。

三 代码

package com.platform.modules.alg.alglib.poj3104;import java.util.Arrays;public class Poj3104 {private int n;private int k;private Integer a[] = new Integer[100005];private String output = "";public Poj3104() {for (int i = 0; i < a.length; i++) {a[i] = 0xFFFFF;}}boolean judge(int x) {int sum = 0;for (int i = 0; i < n; i++) {if (a[i] > x)sum += (a[i] - x + k - 2) / (k - 1); // 上取整if (sum > x)return false;}return true;}void solve() {Integer l = 1, r = a[n - 1], ans = 0;while (l <= r) {int mid = (l + r) >> 1;if (judge(mid)) {ans = mid;r = mid - 1; // 减小} elsel = mid + 1; // 增大}output += ans.toString();output += "\n";}public String cal(String input) {String[] line = input.split("\n");n = Integer.parseInt(line[0]);String[] words = line[1].split(" ");for (int i = 0; i < n; i++) {a[i] = Integer.parseInt(words[i]);}Arrays.sort(a, 0, n - 1);k = Integer.parseInt(line[2]);if (k == 1) {output += a[n - 1].toString();output += "\n";}solve();return output;}
}

四 测试