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

ゝ一世哀愁。 2022-12-19 00:52 86阅读 0赞

非常感谢一位大佬的代码，我才理解了思路，奉上链接  
：https://blog.csdn.net/wuqi5328/article/details/83449834

注意：等待时间的处理（也就是代码中的sum的计算方式）

#include <iostream>
    #include <map>
    #include <string>
    #include <cstdio>
    
    using namespace std;
    const int MAXNUM = 1e4 + 5;
    //用map映射朋友圈， 相同朋友圈的人的映射值相同
    map <string , int> circle;
    
    typedef struct Customer 
    {
        
        //像string vector map 等不定容量的数据类型作为成员变量
        //这个类不能 正常的进行 动态开辟空间
        string name;
        int arrive;
        int deal;
    }Customer, *Queue;
    
    Customer que[MAXNUM];
    int vis[MAXNUM] = {
        0};
    
    int main()
    {
        
        int n, m, num;
        string str;
        int cnt = 0;
        int sum = 0;
        //正在处理业务的用户的离开时间
        int left_time = 0;
        Customer *front_customer = NULL;
        
        cin >> n >> m;
        for (int i = 1; i <= m; i++)
        {
        
            cin >> num;
            while (num--)
            {
        
                cin >> str;
                circle[str] = i;
            }
        }
        for (int i = 0; i < n; i++)
        {
        
            cin >> que[i].name >> que[i].arrive >> que[i].deal;
            if (que[i].deal > 60) que[i].deal = 60;
            //cout << que[i].name << " " << que[i].arrive << " " << que[i].deal << endl;
        }
    
        //cnt记录还剩几个人没处理
        cnt = n;
        //
        cout << que[0].name << endl;
        //标记
        vis[0] = 1;
        //储存 当前正在处理的用户
        front_customer = &que[0];
        left_time = que[0].arrive + que[0].deal;
        cnt--;
    
        while (cnt)
        {
        
            int flag = 0;
            //检查有没有 可以插队的情况
            for (int i = 0; i < n; i++)
            {
        
                if (vis[i] == 1) continue;
                //当访问到 某个用户在 正在处理的用户的离开 之后才到
                //还没有可以插队的 直接退出就行了
                if (que[i].arrive > left_time) break;
                //活到这的 都是 到达时间 小于 队首用户 的离开时间
                if (circle[front_customer->name] == circle[que[i].name])
                {
        
                    flag = 1;
                    vis[i] = 1;
                    cout << que[i].name << endl;
                    sum += left_time - que[i].arrive;
                    left_time += que[i].deal;
                    front_customer = &que[i];
                    break;
                }
            }
            //当前 还不存在插队现象
            if (!flag)
            {
        
                for (int i = 0; i < n; i++)
                {
        
                    if (vis[i] == 1) continue;
                    vis[i] = 1;
                    cout << que[i].name << endl;
                    if (left_time < que[i].arrive) sum += 0;
                    else sum += left_time - que[i].arrive;
                    if (que[i].arrive >= left_time) left_time = que[i].arrive;
                    left_time += que[i].deal;
                    front_customer = &que[i];
                    break;
                }
            }
            cnt--;
        }
        printf("%.1lf\n",(sum*1.0)/n);
        system("pause");
        return 0;
    }