题解 | #晾衣服#

思路 (二分)

将衣服上的水升序排列,在排列中二分搜索最终的答案

即使用lower_bound找到满足条件的最小值

Java AC代码

import java.util.Arrays;
import java.util.Scanner;

/**
 * https://ac.nowcoder.com/acm/problem/235254
 */
public class Main {
    static int n, k;
    static int[] a;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        a = new int[n];
        for (int i = 0; i < n; ++i)
            a[i] = in.nextInt();
        k = in.nextInt() - 1;// 水量每分钟会减小k单位,其中k-1是吹风机吹干的
        Arrays.sort(a);
        if (k == 0) {
            System.out.println(a[n - 1]);
        } else {
            int l = 1, r = a[n - 1];// 二分最终的答案
            while (l < r) {
                int m = l + (r - l >> 1);
                if (check(m))
                    r = m;
                else
                    l = m + 1;
            }
            System.out.println(r);
        }
        in.close();
    }

    private static boolean check(int m) {
        int use = 0;// 吹干使用的时间
        for (int i = 0; i < a.length; i++)
            if (a[i] > m)
                use += Math.ceil(1.0 * (a[i] - m) / k);
        return use <= m;
    }
}