7-6 银行排队问题之单队列多窗口加VIP服务 (30分)（c++）（模拟）

约定不等于承诺〃 2022-12-19 13:09 97阅读 0赞

> 假设银行有K个窗口提供服务，窗口前设一条黄线，所有顾客按到达时间在黄线后排成一条长龙。当有窗口空闲时，下一位顾客即去该窗口处理事务。当有多个窗口可选择时，假设顾客总是选择编号最小的窗口。
> 
> 有些银行会给VIP客户以各种优惠服务，例如专门开辟VIP窗口。为了最大限度地利用资源，VIP窗口的服务机制定义为：当队列中没有VIP客户时，该窗口为普通顾客服务；当该窗口空闲并且队列中有VIP客户在等待时，排在最前面的VIP客户享受该窗口的服务。同时，当轮到某VIP客户出列时，若VIP窗口非空，该客户可以选择空闲的普通窗口；否则一定选择VIP窗口。
> 
> 本题要求输出前来等待服务的N位顾客的平均等待时间、最长等待时间、最后完成时间，并且统计每个窗口服务了多少名顾客。 输入格式:
> 
> 输入第1行给出正整数N（≤1000），为顾客总人数；随后N行，每行给出一位顾客的到达时间T、事务处理时间P和是否VIP的标志（1是VIP，0则不是），并且假设输入数据已经按到达时间先后排好了顺序；最后一行给出正整数K（≤10）——  
> 为开设的营业窗口数，以及VIP窗口的编号（从0到K−1）。这里假设每位顾客事务被处理的最长时间为60分钟。 输出格式:
> 
> 在第一行中输出平均等待时间（输出到小数点后1位）、最长等待时间、最后完成时间，之间用1个空格分隔，行末不能有多余空格。
> 
> 在第二行中按编号递增顺序输出每个窗口服务了多少名顾客，数字之间用1个空格分隔，行末不能有多余空格。 输入样例：
> 
> 10  
> 0 20 0  
> 0 20 0  
> 1 68 1  
> 1 12 1  
> 2 15 0  
> 2 10 0  
> 3 15 1  
> 10 12 1  
> 30 15 0  
> 62 5 1  
> 3 1
> 
> 输出样例：
> 
> 15.1 35 67  
> 4 5 1

写了一天了，掉了好多头发。  
意料之外，debug的时候突然ac了！  
（本来有一份伪代码，但是感觉思路不对，就不展示了）  
对了，对用户、窗口、局部变量的信息更新个人感觉其实可以写成函数的（一个是不需要等待的，一个是需要等待的函数）  
能够节省很多代码  
所以直接上代码吧， 代码里面也有注释和思路：

#include <iostream>
    #include <cstdlib>
    #include <cstdio>
    
    using namespace std;
    const int MAXNUM = 1e3 + 5;
    const int INF = 65535;
    
    typedef struct Window
    {
        
        int next_service_time;
        int num_serviced;
        bool VIPwindow;
    }Window;
    
    typedef struct Customer
    {
        
        int arrive_time;
        int deal_time;
        int wait_time;
        bool VIP;
        bool finished;
    }Customer;
    
    Customer customer[MAXNUM];
    Window window[15];
    int N, K, vip_window;
    
    //code is ok
    void Input()
    {
        
        cin >> N;
        //init and input
        for (int i = 0; i < N; i++)
        {
        
            cin
            >> customer[i].arrive_time
            >> customer[i].deal_time
            >> customer[i].VIP;
            if (customer[i].deal_time > 60) customer[i].deal_time = 60;
            customer[i].finished = false;
            customer[i].wait_time = 0;
        }
        cin >> K >> vip_window;
        for (int i = 0; i < K; i++)
        {
        
            window[i].next_service_time = 0;
            window[i].num_serviced = 0;
            window[i].VIPwindow = false;
        }
        window[vip_window].VIPwindow = true;
    }
    
    //当轮到某VIP客户出列时，若VIP窗口非空，该客户可以选择空闲的普通窗口；否则一定选择VIP窗口
    void solve()
    {
        
        int front_customer = 0;
        int sum_wait = 0;
        int last_finish = 0;
        int max_wait = 0;
        
        while (front_customer < N)
        {
        
            //若该用户已经处理了，则直接跳过
            if (customer[front_customer].finished == true)
            {
        
                front_customer++;
                continue;
            }
    
            //若front是vip用户
            if (customer[front_customer].VIP == true)
            {
        
                //是否需要等待
                bool need_wait = true;
                //不需要等待
                for (int i = 0; i < K; i++)
                {
        
                    if (window[i].next_service_time <= customer[front_customer].arrive_time)
                    {
        
                        need_wait = false;
                        //若VIP窗口也可以提供服务--选择vip窗口
                        if (window[vip_window].next_service_time <= customer[front_customer].arrive_time)
                        {
        
                            //更新用户信息
                            customer[front_customer].finished = true;
                            //更新窗口信息
                            window[vip_window].next_service_time = customer[front_customer].arrive_time + customer[front_customer].deal_time;
                            window[vip_window].num_serviced++;
                            //更新局部变量
    
                            //不需要在循环 查找 合适的窗口了
                            break;
                        }
                        //否则 则进入窗口i
                        else
                        {
        
                            //更新用户信息
                            customer[front_customer].finished = true;
                            //更新窗口信息
                            window[i].next_service_time = customer[front_customer].arrive_time + customer[front_customer].deal_time;
                            window[i].num_serviced++;
                            //不需要在循环 查找 合适的窗口了
                            break;
                        }
                    }
                }
                //需要等待
                if (need_wait == true)
                {
        
                    int Earliest_service_time = INF;
                    int index_window = -1;
                    //找最早开始的窗口
                    for (int i = 0; i < K; i++)
                    {
        
                        if (Earliest_service_time > window[i].next_service_time)
                        {
        
                            Earliest_service_time = window[i].next_service_time;
                            index_window = i;
                        }
                    }
                    //若 VIP窗口 同时开始服务或者在之前提供服务(其实根本不存在小于的情况，因为index_window已经是最小的了)
                    if (window[vip_window].next_service_time <= window[index_window].next_service_time)
                    {
        
                        //更新用户的信息
                        customer[front_customer].wait_time = window[vip_window].next_service_time - customer[front_customer].arrive_time;
                        customer[front_customer].finished = true;
                        //更新窗口的信息
                        window[vip_window].next_service_time += customer[front_customer].deal_time;
                        window[vip_window].num_serviced++;
                        //更新局部变量的信息
                        sum_wait += customer[front_customer].wait_time;
                        max_wait = max(max_wait, customer[front_customer].wait_time);
                    }
                    //若VIP之后开始服务
                    else if (window[vip_window].next_service_time > window[index_window].next_service_time) 
                    {
        
                        //更新用户的信息
                        customer[front_customer].wait_time = window[index_window].next_service_time - customer[front_customer].arrive_time;
                        customer[front_customer].finished = true;
                        //更新窗口的信息
                        window[index_window].next_service_time += customer[front_customer].deal_time;
                        window[index_window].num_serviced++;
                        //更新局部变量的信息
                        sum_wait += customer[front_customer].wait_time;
                        max_wait = max(max_wait, customer[front_customer].wait_time);
                    }
                }
            }
            //若front是普通用户
            else if (customer[front_customer].VIP == false)
            {
        
                //是否需要等待
                bool need_wait = true;
                //不需要等待
                for (int i = 0 ; i < K; i++)
                {
        
                    if (window[i].next_service_time <= customer[front_customer].arrive_time)
                    {
        
                        need_wait = false;
                        bool vip_first = false;
                        //vip用户进入
                        if (window[i].VIPwindow == true)
                        {
        
                            for (int j = front_customer + 1; j < N; j++)
                            {
        
                                //若满足条件的VIP存在
                                if (customer[front_customer].arrive_time == customer[j].arrive_time && customer[j].VIP == true && customer[j].finished == false && window[i].next_service_time <= customer[j].arrive_time)
                                {
        
                                    vip_first = true;
                                    //更新用户信息
                                    customer[j].finished = true;
                                    //更新窗口信息
                                    window[i].next_service_time = customer[j].arrive_time + customer[j].deal_time;
                                    window[i].num_serviced++;
                                    //更新局部变量
    
                                    //保证下次继续访问队首的客户
                                    front_customer--;
                                    break;
                                }
                            }
                        }
                        //front用户进入
                        if (vip_first == false)
                        {
        
                            //更新用户信息
                            customer[front_customer].finished = true;
                            //更新窗口信息
                            window[i].next_service_time = customer[front_customer].arrive_time + customer[front_customer].deal_time;
                            window[i].num_serviced++;
                            //更新局部变量
    
                        }
    
                        break;
                    }
                }
    
                //需要等待
                if (need_wait == true)
                {
        
                    int Earliest_service_time = INF;
                    int index_window = -1;
                    //找最早开始的窗口
                    for (int i = 0; i < K; i++)
                    {
        
                        if (Earliest_service_time > window[i].next_service_time)
                        {
        
                            Earliest_service_time = window[i].next_service_time;
                            index_window = i;
                        }
                    }
    
                    bool vip_first = false;
                    //vip用户进入
                    if (window[index_window].VIPwindow == true)
                    {
        
                        for (int i = front_customer + 1; i < N; i++)
                        {
        
                            if (customer[i].finished == false && customer[i].VIP == true && window[index_window].next_service_time > customer[i].arrive_time)
                            {
        
                                vip_first = true;
                                //更新用户信息
                                customer[i].finished = true;
                                customer[i].wait_time = window[index_window].next_service_time - customer[i].arrive_time;
                                //更新窗口信息
                                window[index_window].next_service_time += customer[i].deal_time;
                                window[index_window].num_serviced++;
                                //更新局部变量信息
                                sum_wait += customer[i].wait_time;
                                max_wait = max(max_wait, customer[i].wait_time);
                                
                                //保证下次继续访问队首的客户
                                front_customer--;
                                //防止第二个vip用户进入，直接退出
                                break;
                            }
                        }
                    }
                    //普通用户进入
                    if (vip_first == false)
                    {
        
                        //更新用户信息
                        customer[front_customer].finished = true;
                        customer[front_customer].wait_time = window[index_window].next_service_time - customer[front_customer].arrive_time;
                        //更新窗口信息
                        window[index_window].next_service_time += customer[front_customer].deal_time;
                        window[index_window].num_serviced++;
                        //更新局部变量信息
                        sum_wait += customer[front_customer].wait_time;
                        max_wait = max(max_wait, customer[front_customer].wait_time);
                    }
                }
            }
            front_customer++;
        }
        
        for (int i = 0; i < K; i++)
        {
        
            last_finish = max(last_finish, window[i].next_service_time);
        }
    
        printf("%.1lf %d %d\n", sum_wait*1.0/N, max_wait, last_finish);
        for (int i = 0; i < K; i++)
        {
        
            if (i) printf(" ");
            printf("%d", window[i].num_serviced);
        }
        printf("\n");
    }
    int main()
    {
        
        //ios::sync_with_stdio(false);
        Input();
        solve();
        system("pause");
        return 0;
    }