Solution Idea

50055. Waiting Time at Supermarket

參考解答

解題想法:

1, 根據題目,因為顧客輸入的順序為到達櫃檯時間之遞增排序,故依序各別處理每個$M_i$即可。

2, 只須記住每位顧客的等待時間,不需要知道在哪個櫃檯結帳或其他資訊,故只要找到目前最早會空閒出來的櫃檯即可。

3, 開一個陣列儲存每個櫃檯最快空閒時間,線性搜尋櫃檯 array ,如果有目前空閒的就直接分配,沒有則找目前最快空閒,並計算等待時間且更新 counter array 。

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
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
 
#define CounterMax 1024
int Counters[CounterMax] = {0};
 
int main(){
    int N, M, sum = 0;
    scanf("%d %d", &N, &M);
    for(int i=0; i<M; i++){
        int time, spend, flag = 0;;
        scanf("%d %d", &time, &spend);
        int min = INT_MAX, minP = -1;
        for(int j=0; j<N; j++){
            if(Counters[j] <= time){
                Counters[j] = time + spend;
                flag = 1;
                break;
            }
            if(Counters[j] < min){
                min = Counters[j];
                minP = j;
            }
        }
        if(flag) continue;
        sum += min - time;
        Counters[minP] += spend;
    }
    printf("%d\n", sum);
    return 0;
}

Advanced

1, Heap Data Structure wiki

線性搜尋找最小值會造成時間複雜度最慘到達 $M \times N$,藉由將 counter array 建構成 Heap data structure 可讓每次找尋最小值及更新一個 counter 的操作複雜度僅 $log(n)$,便可以將整體時間複雜度降至 $M \times log(n)$

Discussion