PAT 银行排队问题之单窗口“夹塞”版(队列+模拟)解题报告

2017-03-08 669 次浏览 解题报告

解题思路

题面中提到后面的人可以找前面的是朋友的人夹塞,让朋友帮忙办理业务,朋友的办理时间会累加。这个过程可以看作一个插队的过程,即把自己插到朋友的后面。由于朋友帮自己办业务是紧接着他自己刚办完的业务连续办理的,所以自己插在朋友后面和让朋友累加办理时间是等价的。

因此我们可以使用队列模拟,每次 pop 出队首,表示此人已办理完毕。接下来找一个人放到队列中作为下一个要办理的人。而下一个的人选是有要求的,即优先寻找一个到达时间不晚于自己离开时间的朋友,让他排在自己后面(插队),如果找不到则按原顺序找自己后面的第一个人,让他排在自己后面。这样不断循环并累加等待时间,直到队列为空即可。

参考代码

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

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

int Hash(char *s) { // 把字符串哈希成数字,防止超时
    return (s[0]-'A')*26*26 + (s[1]-'0')*26 + s[0]-'0';
}

int main(int argc, char const *argv[]) {
    int n, m, l;
    char s[4];
    bool vis[10000] = {false}; // 标记是否已办理完毕
    scanf("%d %d", &n, &m);
    set<int> st[100]; // 朋友圈集合
    map<int, int> mp; // 映射人名到朋友圈编号
    for(int i=0; i<m; ++i) {
        scanf("%d", &l);
        while(l--) {
            scanf("%s", s);
            st[i].insert(Hash(s));
            mp[Hash(s)] = i;
        }
    }
    for(int i=0; i<n; ++i) {
        scanf("%s %d %d", a[i].name, &a[i].t, &a[i].p);
        if(a[i].p > 60) a[i].p = 60;
    }
    queue<info> q;
    q.push(a[0]);
    vis[0] = true;
    int last = a[0].t+a[0].p;
    int sum = 0;
    while(!q.empty()) {
        info f = q.front();
        q.pop();
        printf("%s\n", f.name);
        bool found = false;
        for(int i=1; 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=1; i<n; ++i) {
                if(vis[i]) continue;
                q.push(a[i]);
                vis[i] = true;
                sum += max(0, last-a[i].t); // 等待时间可能为 0(窗口空闲一段时间)
                if(a[i].t > last) last = a[i].t;
                last += a[i].p;
                break;
            }
        }
    }
    printf("%.1f\n", 1.0*sum/n);
    
    return 0;
}

还不快抢沙发

添加新评论