Drying (POJ 3104)

Using binary search method to guess a drying value first and then we can use greedy strategy to verify if the guessed value is feasible. If the ith cloth contains A[i] amount of water and the guest value if m, then that cloth will be totally dry if (m - x) + x * k >= A[i] where x is the minues we spend using radiator. Whis this formula we can find the minium value of x for this cloth. For each cloth we apply this formular and add up all the minutes of radiator usage needed. If the minutes is less than m, then the solution is valid, or it is not feasible.

If a guessed value is feasible, we should try decrease the guess to find a minimum value, or we increase it.

import java.io.*;
import java.util.*;

public class Drying {
    private static boolean canDry(int[] things, int t, int k) {
        int tl = t;

        if (k == 1) return (things[things.length - 1] <= t);

        for (int i = things.length - 1; i >= 0; i--) {
            int a = things[i];
            if (a <= t) return true;
            int d = (a - t) / (k - 1);
            if ((a - t) % (k - 1) != 0) d++;
            if (d <= tl) tl -= d;
            else return false;
        }
        return true;
    }
    private static void solve(int[] things, int K) {
        int l = 0, u = 1000000000;
        while (l <= u) {
            int t = (l + u) / 2;
            if (canDry(things, t, K)) u = t - 1;
            else l = t + 1;
        }
        System.out.println(l);
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int N = in.nextInt();
            int[] things = new int[N];
            for (int i = 0; i < N; i++) things[i] = in.nextInt();
            Arrays.sort(things);
            int K = in.nextInt();
            solve(things, K);
        }
    }
}