多处最优服务次序问题——算法设计与分析（C实现）

待我称王封你为后i 2024-03-22 11:48 43阅读 0赞

**问题描述**：设有n个顾客同时等待一项服务。顾客i需要的服务时间为![t\_\{i\}(1\\leq i\\leq n)][t_i_1_leq i_leq n]，共有s处可以提供此项服务。应该如何安排n个顾客的服务次序，才能使平均等待时间达到最小？平均等待时间是n个顾客的等待服务时间的总和除以n。

**算法设计：**对于给定的n个顾客需要的服务时间和s的值，计算最优服务次序。

**数据输入**：由文件input.txt给出输入数据。第1行有2个正整数n和s，表示有n个顾客且有s处可以提供服顾客需要的服务。接下来的1行中有n个正整数，表示n个顾客需要的服务时间。

**结果输出：**将计算的最小平均等到时间输出到文件output.txt。

基本思想：

*  该题是贪心算法的典型，只需要将所有的任务按照截至时间递增进行排序，然后将任务逐个分配给每一个服务器。即将等待的人逐个分配到每一个服务处。
 *  重在于统计每一个任务等待时间，然后**计算平均等待时间**。
 *  需要注意的是，这里的等待时间是相对于完成任务的时间点，**等待时间包括完成任务所花费的时间和等待分配到的时间，即等待时间=执行时间+执行前等待分配的时间**

**具体代码实现如下：**

#include<stdio.h>
    
    //选出当前等待时间最小的服务处 
    int SelectMin(int* wait,int s)
    {
        int min = wait[0];
        int index = 0;
        for (int i = 0; i < s; i++) 
    	{
            if (min > wait[i]) 
    		{
                min = wait[i];
                index = i;
            }
        }
        return index;
    }
    
    //安排顾客，计算平均等待时间 
    int Greedy(int* wait, int *arr, int n,int s) 
    {
        int sum = 0;
        int index;
        for (int i = 0; i < n; i++) 
    	{
            index = SelectMin(wait, s);
            wait[index] += arr[i];
            sum += wait[index];
        }
        return sum / n;	
    }
    
    //对顾客的执行时间进行从小到大的排序 
    void sort(int* arr,int n)
    {
    	int temp;
    	 for(int i=0;i<n;i++)
            {
                for(int j=0;j<i;j++)
                {
                    if(arr[j]>arr[j+1])
                    {
                        temp=arr[j];
                        arr[j]=arr[j+1];
                        arr[j+1]=temp;
                        }
                 }
            }
    }
    
    
    int main()
    {
        int n,s,res;
        
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        
        scanf("%d %d",&n,&s);//从文件中取出顾客人数和服务处数量 
        
        int wait[s];
        int arr[n];
        
        for(int i=0;i<n;i++)
        {
        	scanf("%d",&arr[i]);
    	}
        
        sort(arr, n);		
        res= Greedy(wait, arr, n, s);
    
         printf("%d",res);
        return 0;
    }

现在让我们来检验一下代码的正确性：

（1）首先在**程序所在路径下**建立两个题目所需要的文本文件：input.txt output.txt

![f9e5d864bad44531a4d20c3b72c44f1c.png][]

（2）在input.txt文件中输入相关数据：

![acc25553d63442e2a6a77d04b41e0b99.png][]

（3）将代码运行起来，下图为代码运行成功的标志：

![9d389d0f32b642c78157ebbef77dc340.png][]

（4）那么接下来我们进入输出文件output.txt，查看代码运行的具体效果

![b0d75713b75c4375af15e02b8b7e4f6e.png][]

经过检验发现，该代码实现的该实例时正确的，大家可以对其他实例进行一个验证，也可可以将代码自行更改，增加其可行性~

[t_i_1_leq i_leq n]: https://latex.csdn.net/eq?t_%7Bi%7D%281%5Cleq%20i%5Cleq%20n%29
[f9e5d864bad44531a4d20c3b72c44f1c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/9562bf4ba8c847d8b7d17bafaf8287ea.png
[acc25553d63442e2a6a77d04b41e0b99.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/33f1b08735634dfc953cb60569070163.png
[9d389d0f32b642c78157ebbef77dc340.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/ecfd934e2e534827acf5d9a067c75f21.png
[b0d75713b75c4375af15e02b8b7e4f6e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/47f7edb564d84fe381b2ca28106b874e.png