PAT 銀行排隊問題之單視窗“夾塞”版 (隊列+模拟) -- 解題報告

解題思路

題面中提到後面的人可以找前面的是朋友的人夾塞，讓朋友幫忙辦理業務，朋友的辦理時間會累加。這個過程可以看作一個插隊的過程，即把自己插到朋友的後面。由于朋友幫自己辦業務是緊接着他自己剛辦完的業務連續辦理的，是以自己插在朋友後面和讓朋友累加辦理時間是等價的。

是以我們可以使用隊列模拟，每次 pop 出隊首，表示此人已辦理完畢。接下來找一個人放到隊列中作為下一個要辦理的人。而下一個的人選是有要求的，即優先尋找一個到達時間不晚于自己離開時間的朋友，讓他排在自己後面（插隊），如果找不到則按原順序找自己後面的第一個人，讓他排在自己後面。這樣不斷循環并累加等待時間，直到隊列為空即可。

參考代碼

#include <cstdio>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
using namespace std;

struct info {
    char name[];
    int t;
    int p;
} a[];

int Hash(char *s) { // 把字元串哈希成數字，防止逾時
    return (s[]-'A')** + (s[]-'0')* + s[]-'0';
}

int main(int argc, char const *argv[]) {
    int n, m, l;
    char s[];
    bool vis[] = {false}; // 标記是否已辦理完畢
    scanf("%d %d", &n, &m);
    set<int> st[]; // 朋友圈集合
    map<int, int> mp; // 映射人名到朋友圈編号
    for(int i=; i<m; ++i) {
        scanf("%d", &l);
        while(l--) {
            scanf("%s", s);
            st[i].insert(Hash(s));
            mp[Hash(s)] = i;
        }
    }
    for(int i=; i<n; ++i) {
        scanf("%s %d %d", a[i].name, &a[i].t, &a[i].p);
        if(a[i].p > ) a[i].p = ;
    }
    queue<info> q;
    q.push(a[]);
    vis[] = true;
    int last = a[].t+a[].p;
    int sum = ;
    while(!q.empty()) {
        info f = q.front();
        q.pop();
        printf("%s\n", f.name);
        bool found = false;
        for(int i=; i<n; ++i) { // 尋找一個到達時間不晚于自己辦理結束時間的朋友
            if(vis[i]) continue;
            if(a[i].t > last) break;
            if(st[mp[Hash(f.name)]].count(Hash(a[i].name))) {
                q.push(a[i]);
                vis[i] = true;
                found = true;
                sum += last-a[i].t;
                last += a[i].p;
                break;
            }
        }
        if(!found) { // 未找到，則按原順序找下一個人
            for(int i=; i<n; ++i) {
                if(vis[i]) continue;
                q.push(a[i]);
                vis[i] = true;
                sum += max(, last-a[i].t); // 等待時間可能為 0（視窗空閑一段時間）
                if(a[i].t > last) last = a[i].t;
                last += a[i].p;
                break;
            }
        }
    }
    printf("%.1f\n", *sum/n);

    return ;
}