7-4 银行排队问题之单窗口“夹塞”版（30 分）

题目：

排队“夹塞”是引起大家强烈不满的行为，但是这种现象时常存在。在银行的单窗口排队问题中，假设银行只有1个窗口提供服务，所有顾客按到达时间排成一条长龙。当窗口空闲时，下一位顾客即去该窗口处理事务。此时如果已知第

$输入格式：$

$输入的第一行是两个整数：$

输出格式：

按顾客接受服务的顺序输出顾客名字，每个名字占1行。最后一行输出所有顾客的平均等待时间，保留到小数点后1位。

思路：

题目整体的思路并不是很难，但需要注意的细节有点多。

1、对于每个朋友圈，我们可以对每一个客户进行编号，然后用并查集来储存每一个朋友圈。

2、首先让第一个到达的客户进行处理业务，对之后的客户分两个情况处理

（1）后边在当前客户的业务处理之前，有加塞客户到来，依次处理这些加塞客户

（2）没有加塞客户到来的话，就去处理按正常顺序来的下一个客户，然后循环步骤2

3、每处理一个客户相应的就更新下窗口当前业务的结束时间和当前窗口处理的客户的编号。

代码：

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 1e4+10;
struct Peo {
    string name;
    int arrive;
    int timeNeed;
    int waitTime;
    bool vis;
} p[maxn];
map<string, int> mp;
vector<string> v[110];
queue<Peo> que;
int m,n,k;
int pre[maxn];

void init(){
    for(int i = 0; i<110; i++)
        v[i].clear();
    while(!que.empty()) que.pop();
    for(int i = 0; i<maxn; i++){//对每一个客户进行编号，后边并查集存朋友圈会用到
        pre[i] = i;
    }
}

int Find(int x){
    return x==pre[x] ? x : pre[x] = Find(pre[x]);
}

void putIn(){
    string name;
    cin>>m>>n;
    for(int i = 0; i<n; i++){//输入朋友圈
        cin>>k;
        for(int j = 0; j<k; j++){
            cin>>name;
            v[i].push_back(name);
        }
    }
    for(int i = 0; i<m; i++){//输入每一个客户的有关信息
        cin>>p[i].name>>p[i].arrive>>p[i].timeNeed;
        if(p[i].timeNeed>60)
            p[i].timeNeed = 60;
        p[i].waitTime = 0;
        p[i].vis = false;
        mp[p[i].name] = i;
    }
    for(int i = 0; i<n; i++){//对给出的朋友圈，用并查集储存
        int tx = Find(mp[v[i][0]]);
        for(int j = 1; j<v[i].size(); j++){
            int ty = Find(mp[v[i][j]]);
            if(tx!=ty)
                pre[ty] = tx;
        }
    }
}

void solve(){
    int endTime = p[0].arrive+p[0].timeNeed,curId = 0;//endTime是窗口当前业务结束的时间,curId是当前正在
    p[0].vis = true;                                 //处理业务的客户
    p[0].waitTime = 0;
    que.push(p[0]);
    while(1){
        bool isFind = false;
        for(int i = 1; i<m; i++){//处理加塞的人(即与当前所有与正在处理业务的客户在一个朋友圈的人)
            int tx = Find(i),ty = Find(curId);
            if(tx==ty && !p[i].vis && p[i].arrive <= endTime){//这个客户必须没有访问过，而且是在他朋友结束前到来
                p[i].vis = true;
                que.push(p[i]);//压入答案队列
                p[i].waitTime = endTime-p[i].arrive;//更新这个客户的等待时间
                endTime = endTime+p[i].timeNeed;//更新窗口的当前业务的结束时间
                curId = i;//更新窗口当前客户的id
                isFind = true;//说明有加塞的客户出现
            }
        }
        if(!isFind){//没有加塞的客户的话,就去处理其余的客户
            for(int i = 1; i<m; i++){
                int tx = Find(i),ty = Find(curId);
                if(tx!=ty && !p[i].vis){
                    p[i].vis = true;
                    que.push(p[i]);
                    if(p[i].arrive<=endTime){//根据这个客户到达时间的不同分别更新客户的等待时间
                        p[i].waitTime = endTime-p[i].arrive;//窗口的结束时间
                        endTime = endTime+p[i].timeNeed;
                        curId = i;
                    }
                    else{
                        p[i].waitTime = 0;
                        endTime = p[i].arrive+p[i].timeNeed;
                        curId = i;
                    }
                    break;//这种不加塞的客户只要找到一个就可以了,然后进入下一个循环去处理与这个客户有关的加塞客户
                }
            }
        }
        if(que.size() == m)
            break;
    }
    while(!que.empty()){
        cout<<que.front().name<<endl;
        que.pop();
    }
    double sum = 0;
    for(int i = 0; i<m; i++){//遍历所有的客户,求等待时间的和,求平均值
        sum += p[i].waitTime;
    }
    printf("%.1f
",sum/m);
    return;
}

int main() {
    init();
    putIn();
    solve();
    return 0;
}
/*
putIn:
6 2
3 ANN BOB JOE
2 JIM ZOE
JIM 0 20
BOB 0 15
ANN 0 30
AMY 0 2
ZOE 1 61
JOE 3 10
putOut:
JIM
ZOE
BOB
ANN
JOE
AMY
75.2
*/

View Code

7-4 银行排队问题之单窗口“夹塞”版 （30 分）

7-4 银行排队问题之单窗口“夹塞”版（30 分）