咖啡问题 ☕️

给定一个数组 Arr，Arr[i]代表第 i 号咖啡机泡一杯咖啡的时间 给定一个正数 N，表示 N 个人等着咖啡机泡咖啡，每台咖啡机只能轮流泡咖啡 只有一台咖啡机，一次只能洗一个杯子，时间耗费 a，洗完才能洗下一杯 假设所有人拿到咖啡之后立刻喝干净，返回从开始等到所有咖啡机变干净的最短时间 三个参数：int[] Arr，int N，int a，int b

暴力解（每个人都尝试泡一杯咖啡 很慢很慢） #

/**
 * 纯暴力的对数器
 *
 * @param arr
 * @param n
 * @param a
 * @param b
 * @return
 */
public static int right(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);
}

private 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;
}

private 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, washLine, 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(ans2, ans1);
}

贪心优化后的暴力 #

public static class Machine {
  public int timePoint;
  public int workTime;

  public Machine(int t, int w) {
    timePoint = t;
    workTime = w;
  }
}

public static int minTime1(int[] arr, int n, int a, int b) {
  PriorityQueue<Machine> heap = new PriorityQueue<Machine>(
      (o1, o2) -> (o1.timePoint + o1.workTime) - (o2.timePoint + o2.workTime));

  for (int i = 0; i < arr.length; i++)
    heap.add(new Machine(0, arr[i]));

  int[] drinks = new int[n];
  for (int i = 0; i < n; i++) {
    Machine cur = heap.poll();
    cur.timePoint += cur.workTime;
    drinks[i] = cur.timePoint;
    heap.add(cur);
  }
  return bestTime(drinks, a, b, 0, 0);
}

/**
 * @param drinks 所有杯子可以开始洗的时间
 * @param wash   单杯洗干净的时间（串行）
 * @param air    挥发干净的时间(并行)
 * @param index
 * @param free   洗的机器什么时候可用
 * @return drinks[index.....]都变干净，最早的结束时间（返回）
 */
private static int bestTime(int[] drinks, int wash, int air, int index, int free) {
  if (index == drinks.length) {
    return 0;
  }
  // index号杯子 决定洗
  int selfClean1 = Math.max(drinks[index], free) + wash;
  int restClean1 = bestTime(drinks, wash, air, index + 1, selfClean1);
  int p1 = Math.max(selfClean1, restClean1);

  // index号杯子 决定挥发
  int selfClean2 = drinks[index] + air;
  int restClean2 = bestTime(drinks, wash, air, index + 1, free);
  int p2 = Math.max(selfClean2, restClean2);
  return Math.min(p1, p2);
}

动态规划 #

/**
   * 动态规划
   *
   * @param arr
   * @param n
   * @param a
   * @param b
   * @return
   */
  public static int minTime2(int[] arr, int n, int a, int b) {
    PriorityQueue<Machine> heap = new PriorityQueue<Machine>(
        (o1, o2) -> (o1.timePoint + o1.workTime) - (o2.timePoint + o2.workTime));
    for (int i = 0; i < arr.length; i++) {
      heap.add(new Machine(0, arr[i])); // 初始化，泡咖啡机的工作时间进小根堆
    }

    int[] drinks = new int[n];
    for (int i = 0; i < n; i++) {
      Machine cur = heap.poll();
      cur.timePoint += cur.workTime;
      drinks[i] = cur.timePoint;
      heap.add(cur);
    }
    return dp(drinks, a, b);
  }

  public static int dp(int[] drinks, int wash, int air) {
    int N = drinks.length;
    int maxFree = 0;
    for (int i = 0; i < drinks.length; i++) {
      maxFree = Math.max(maxFree, drinks[i]) + wash;
    }
    int[][] dp = new int[N + 1][maxFree + 1];
    for (int index = N - 1; index >= 0; index--) {
      for (int free = 0; free <= maxFree; free++) {
        int selfClean1 = Math.max(drinks[index], free) + wash;
        if (selfClean1 > maxFree) {
          break; // 因为后面的也都不用填了
        }
        // index号杯子 决定洗
        int restClean1 = dp[index + 1][selfClean1];
        int p1 = Math.max(selfClean1, restClean1);
        // index号杯子 决定挥发
        int selfClean2 = drinks[index] + air;
        int restClean2 = dp[index + 1][free];
        int p2 = Math.max(selfClean2, restClean2);
        dp[index][free] = Math.min(p1, p2);
      }
    }
    return dp[0][0];
  }