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 i
th 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);
}
}
}