1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
| public static int minTime(int[] arr, int n, int a, int b) { int[] times = new int[arr.length]; int[] drink = new int[n]; return forceMake(arr, times, 0, drink, n, a, b); }
public static int forceMake(int[] arr, int[] times, int kth, int[] drink, int n, int a, int b) { if (kth == n) { int[] drinkSorted = Arrays.copyOf(drink, kth); Arrays.sort(drinkSorted); return forceWash(drinkSorted, a, b, 0, 0, 0); } int time = Integer.MAX_VALUE; for (int i = 0; i < arr.length; i++) { int work = arr[i]; int pre = times[i]; drink[kth] = pre + work; times[i] = pre + work; time = Math.min(time, forceMake(arr, times, kth + 1, drink, n, a, b)); drink[kth] = 0; times[i] = pre; } return time; }
public static int forceWash(int[] drinks, int a, int b, int index, int washLine, int time) { if (index == drinks.length) { return time; } int wash = Math.max(drinks[index], washLine) + a; int ans1 = forceWash(drinks, a, b, index + 1, wash, Math.max(wash, time));
int dry = drinks[index] + b; int ans2 = forceWash(drinks, a, b, index + 1, washLine, Math.max(dry, time)); return Math.min(ans1, ans2); }
|