泡咖啡問題

2022-10-26 06:01:10

泡咖啡問題

作者:Grey

原文地址:

部落格園:泡咖啡問題

CSDN:泡咖啡問題

題目描述

陣列 arr 中記錄每個咖啡機制造一杯咖啡的時間,假設有 m 個人,都在 0 號時間點開始排隊,返回一個長度為 m 的陣列,代表每個人得到咖啡的時間,

要求:最後一個得到咖啡的人的時間儘可能短。

主要思路

定義咖啡機這個資料結構

    public static class CoffeeMachine {
       
        public int start;
        public int work;

        public CoffeeMachine(int s, int w) {
            start = s;
            work = w;
        }
        @Override
        public String toString() {
            return "CoffeeMachine{" + "start=" + start + ", work=" + work + '}';
        }

    }

其中

start 變數表示這個咖啡機什麼時候可以空閒,

work 變數表示這個咖啡機制作一杯咖啡的時間,

接下來,設定一個小根堆(Java 中就是 PriorityQueue),小根堆存放的就是咖啡機的資訊,小根堆的比較策略就是:咖啡機開始工作的時間加上這個咖啡機制作一杯咖啡的時間之和越小的在堆頂。

每次做完一杯咖啡以後,彈出,記錄下此時的時間存入結果陣列,並且修改此時的咖啡機的開始工作時間,再次壓入小根堆,然後小根堆彈出下一個元素,如此往復,一直到小根堆彈出 m 個元素。

例如

首先把所有咖啡機放入小根堆,第一個彈出的咖啡機是 CoffeeMachine{start=0, work=2}

0 號小人使用 CoffeeMachine{start=0, work=2} 咖啡機

此時這個咖啡機的引數變為 CoffeeMachine{start=2, work=2}

把改變後的咖啡機放入小根堆,再次彈出一個咖啡機,此時

CoffeeMachine{start=0, work=3} 咖啡機被彈出

1 號人使用 CoffeeMachine{start=0, work=3} 咖啡機

此時這個咖啡機的引數變為 CoffeeMachine{start=3, work=3}

把改變後的咖啡機放入小根堆,再次彈出一個咖啡機,此時

CoffeeMachine{start=2, work=2} 咖啡機被彈出

2 號人使用 CoffeeMachine{start=2, work=2} 咖啡機

此時這個咖啡機的引數變為 CoffeeMachine{start=4, work=2}

把改變後的咖啡機放入小根堆,再次彈出一個咖啡機,此時

CoffeeMachine{start=0, work=5} 咖啡機被彈出

3 號人使用 CoffeeMachine{start=0, work=5} 咖啡機

此時這個咖啡機的引數變為 CoffeeMachine{start=5, work=5}

把改變後的咖啡機放入小根堆,再次彈出一個咖啡機,此時

CoffeeMachine{start=4, work=2} 咖啡機被彈出

4 號人使用 CoffeeMachine{start=4, work=2} 咖啡機

此時這個咖啡機的引數變為 CoffeeMachine{start=6, work=2}

完整程式碼如下


import java.util.PriorityQueue;

public class Code_Coffee {
    public static class CoffeeMachine {
        @Override
        public String toString() {
            return "CoffeeMachine{" + "start=" + start + ", work=" + work + '}';
        }

        public int start;
        public int work;

        public CoffeeMachine(int s, int w) {
            start = s;
            work = w;
        }

    }

    public static int[] bestChoices(int[] arr, int m) {
        int[] ans = new int[m];
        PriorityQueue<CoffeeMachine> heap = new PriorityQueue<>((o1, o2) -> o1.start + o1.work - o2.start - o2.work);
        for (int coffeeWork : arr) {
            // 製造咖啡最短時間的咖啡機在堆頂
            heap.add(new CoffeeMachine(0, coffeeWork));
        }
        for (int i = 0; i < m; i++) {
            CoffeeMachine cur = heap.poll();
            // 第i號人使用cur這個咖啡機,所以cur這個咖啡機的開始時間變為cur.start + cur.work
            System.out.println(i + " 號人使用 " + cur + "咖啡機");
            ans[i] = cur.start + cur.work;
            System.out.println(i + " 號人在 [" + cur.start + "] 時刻搞定完一杯咖啡");
            cur.start = ans[i];
            heap.add(cur);
        }
        return ans;
    }

    public static void main(String[] args) {
        int m = 5;
        int[] arr = {2, 3, 5};
        bestChoices(arr, m);
    }
}

更多

演演算法和資料結構筆記