7-5 银行排队问题之单队列多窗口服务 (25分)(c++)

末蓝、 2022-12-19 08:59 68阅读 0赞

首先，先感谢这位大佬的代码：https://www.cnblogs.com/sykline/p/9816874.html  
注释易懂，思路清晰。  
以下思路和代码都是参考他的

> 假设银行有K个窗口提供服务，窗口前设一条黄线，所有顾客按到达时间在黄线后排成一条长龙。当有窗口空闲时，下一位顾客即去该窗口处理事务。当有多个窗口可选择时，假设顾客总是选择编号最小的窗口。
> 
> 本题要求输出前来等待服务的N位顾客的平均等待时间、最长等待时间、最后完成时间，并且统计每个窗口服务了多少名顾客。 输入格式:
> 
> 输入第1行给出正整数N（≤1000），为顾客总人数；随后N行，每行给出一位顾客的到达时间T和事务处理时间P，并且假设输入数据已经按到达时间先后排好了顺序；最后一行给出正整数K（≤10），为开设的营业窗口数。这里假设每位顾客事务被处理的最长时间为60分钟。  
> 输出格式:
> 
> 在第一行中输出平均等待时间（输出到小数点后1位）、最长等待时间、最后完成时间，之间用1个空格分隔，行末不能有多余空格。
> 
> 在第二行中按编号递增顺序输出每个窗口服务了多少名顾客，数字之间用1个空格分隔，行末不能有多余空格。 输入样例：
> 
> 9  
> 0 20  
> 1 15  
> 1 61  
> 2 10  
> 10 5  
> 10 3  
> 30 18  
> 31 25  
> 31 2  
> 3  
> 输出样例：
> 
> 6.2 17 61  
> 5 3 1

思路：我用伪代码来展示

int front_customer = 0;
    int num_customers;
    int num_windows;
    
    窗口
    {
        
    	left_time = 0;
    
    } window;
    
    用户
    {
        
    	arrive_time
    	deal_time
    	wait
    }
    
    输入()
    {
        
    	num_customers;
    	
    	cin >> num_customers;
    	for()
    	{
        
    		每条用户的arrive_time和deal_time;
    		每条用户的wait = 0
    	}
    
    	cin >> num_windows;
    	for()
    	{
        
    		每个窗口的完成服务的时间 = 0；
    		每个窗口的服务人数 = 0；
    	}
    }
    
    void solve()
    {
        
    	int maxwaite = 0;
    	int sum_waite = 0;
    	lastFinish = 0;
    	while (front_customer < num_customers)
    	{
        
    		是否 需要等待 bool need_wait? 
    		访问的窗口下标 index_window;
    		最晚结束 处理时间 minEnd_time_provide_service;
    		for (int i = 0; i < K; i++)
    		{
        
    			//不需要等待
    			if (用户i的到达时间 >= 窗口index的结束时间)
    			{
        
    				更新这个窗口的信息
    				{
        
    					再次提供服务时间 = 用户i的到达时间 + 用户i的处理时间
    					窗口服务人数++；
    				}
    				need_wait? = false;
    				
    				break;
    			}
    			//需要等待
    			else 
    			{
        
    				if (最早提供服务的时间 > 当前用户的再次提供服务的时间)
    				{
        
    					更新最早提供服务的时间
    					index_window = i;
    				}
    			}
    		}
    		if (need_wait? == true)
    		{
        
    			customer[front_customer].wait = 窗口再次提供服务的时间 - 用户fron的到达时间
    			sum_waite += customer[front_customer].wait;
    			最大等待时间 = max(maxwaite, customer[front_customer].wait)
    			更新这个窗口的信息
    			{
        
    				再次提供服务时间 = 用户i的到达时间 + 用户i的处理时间
    				窗口服务人数++；
    			}
    		}
    		front_customer++;
    	}
    	最晚 完成 时间 需要从 窗口对象中获得
    	输出平均等待时间 最大等待时间 最晚完成时间
    	输出每个窗口的服务人数 
    }
    
    int main()
    {
        
    	输入();
    	solve();
    }

ac代码：

#include <iostream>
    #include <cstdlib>
    #include <algorithm>
    #include <cstdio>
    
    using namespace std;
    const int MAXNUM = 1e3 + 5;
    const int INF = 65535;
    
    typedef struct Window
    {
        
        int next_service_delivery_time;
        int num_of_people_served;
    }Window;
    
    typedef struct
    {
        
        int arrive_time;
        int deal;
        int wait;
    }Customer;
    
    Customer customer[MAXNUM];
    Window window[15];
    
    int N, K;
    void Input()
    {
        
        
        cin >> N;
        for (int i = 0; i < N; i++)
        {
        
            cin >> customer[i].arrive_time;
            cin >> customer[i].deal;
            if (customer[i].deal > 60) 
                customer[i].deal = 60;
            customer[i].wait = 0;
        }
        cin >> K;
        for (int i = 0; i < K; i++)
        {
        
            window[i].next_service_delivery_time = 0;
            window[i].num_of_people_served = 0;
        }
    }
    
    void solve()
    {
        
        int maxwait = 0;
        int sum_wait = 0;
        int lastFinish = 0;
        int front_customer = 0;
    
        while (front_customer < N)
        {
        
            bool need_wait = true;
            int index_window = -1;
            int mintime_provide_service = INF;
    
            for (int i = 0; i < K; i++)
            {
        
                if (customer[front_customer].arrive_time >= window[i].next_service_delivery_time)
                {
        
                    window[i].next_service_delivery_time = 
                    customer[front_customer].arrive_time + 
                    customer[front_customer].deal;
    
                    window[i].num_of_people_served++;
                    need_wait = false;
                    break;
                }
                else 
                {
        
                    if (mintime_provide_service > window[i].next_service_delivery_time)
                    {
        
                        mintime_provide_service = window[i].next_service_delivery_time;
                        index_window = i;
                    }
                }
            }
            if (need_wait == true)
            {
        
                customer[front_customer].wait += 
                window[index_window].next_service_delivery_time - customer[front_customer].arrive_time;
                sum_wait += customer[front_customer].wait;
                maxwait = max(maxwait, customer[front_customer].wait);
    
                window[index_window].next_service_delivery_time += 
                customer[front_customer].deal;
    
                window[index_window].num_of_people_served++;
            }
            front_customer++;
        }
        for (int i = 0; i < K; i++)
        {
        
            lastFinish = max(lastFinish, window[i].next_service_delivery_time);
        }
        printf("%.1lf %d %d\n", sum_wait*1.0/N, maxwait, lastFinish);
        for (int i = 0; i < K; i++)
        {
        
            if (i) printf(" ");
            printf("%d", window[i].num_of_people_served);
        }
        printf("\n");
    
    }
    int main()
    {
        
        //ios::sync_with_stdio(false);
        Input();
        solve();
        system("pause");
        return 0;
    }