多处最优服务次序问题（贪心）

清疚 2023-06-13 04:46 22阅读 0赞

#### 问题描述 ####

设有n个顾客等待服务，有k处可以提供这个服务，确定最优服务次序，让顾客平均等待时间最少，这个平均等待时间就是顾客们等待的总和/n。

#### input ####

第一行输入n，k，表示n名顾客，k处服务店  
第二行分别输入n个整数，表示每名顾客所需要的服务时间。

#### out ####

输出最少平均等待时间

#### 输入样例 ####

> 10 2  
> 56 12 1 99 1000 234 33 55 99 812

#### 输出样例 ####

> 336

#### 思路 ####

1.  贪心，对于本题，如果想让大家等待的时间最少，就应该从小到大排序，让需要服务时间最短的人先被服务。
2.  模拟，有k处可以提供这个服务，刚开始k处都是空的，那就取前k个人被服务，剩下的n-k个就要等待，需要等待的时间是k个正在被服务人中最小的那个，因为它最先出来，比如他的时间是s，每次都模拟那个最先完成服务的人出来，k处剩下的k-1个人都应该减去s，然后放进去新的一个人，不断的模拟，累加上等待的时间。
3.  刚开始输入样例的时候，等待时间就应该加上所有的输入样例，因为一个人在被服务的时候，虽然他没等别人，但是他等了自己哈哈哈

#### C++ AC ####

我们模拟成理发店，我们都知道理发店里有很多座位可以理发。  
我们可以假设等待服务的这帮人都是剃头的。会不会好想一点？

#include <iostream>
    #include <bits/stdc++.h>
    using namespace std;
    //标记坐在理发椅上的几个人中最先结束的(服务时间剩的最少的)
    int min_value;
    //对应上面那个的，在理发店中的位置
    int min_loc;
    
    //用于找到那个最先理好的
    void getMin(vector<int> v)
    {
        
        min_value=v[0];
        min_loc=0;
        for(int i=0;i<v.size();i++)
        {
        
            if(v[i]<min_value)
            {
        
                min_value=v[i];
                min_loc=i;
            }
        }
    }
    int main()
    {
        
        //存放每个人理发需要的时间
        int arr[100];
        //用来加时间
        int time=0;
        //保存在理发椅上的人
        vector<int> v;
        int n,k;
        cin>>n>>k;
        for(int i=0;i<n;i++)
        {
        
            cin>>arr[i];
            time+=arr[i];//因为自己被理发也算是自己在等待
        }
        //贪心从小到大排序，我们要贪的是理发时间最短的最先被理发，
        //这样大家平均等待时间就少了
        sort(arr,arr+n);
    
        //因为刚开始理发店是空的，把前k个放进理发店(vector)中
        for(int i=0;i<k;i++)
        {
        
            v.push_back(arr[i]);
        }
        //标记
        int i=k;
        while(true)
        {
        
            //找那个最早被理完的人
            getMin(v);
            //让时间累加上其他等着的人等待的时间，
            //后面这个n-i是控制等待的人数
            time+=min_value*(n-i);
            //除了最先被理完的那个人的，
            //其他几个正在被服务的人，减去这个最先被理完的人的时间
            for(int j=0;j<v.size();j++)
            {
        
                if(j!=min_loc)
                {
        
                    v[j]-=min_value;
                }
            }
            //让那个最小值，也就是最先被服务完的出来，换成等着理发的
            v[min_loc]=arr[i];
            //指针指向下一个待服务的人
            i++;
    
            //结束条件
            if(i==n)
            {
        
                break;
            }
        }
        cout<<time/n<<endl;
        return 0;
    }