一 问题描述

二 算法设计

可以用二分法来求最少用的时间，关键地方是用 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; // 减小
            } else
                l = 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;
    }
}

四 测试