问题描述：
设有n（1≤n≤100）个顾客同时等待一项服务。顾客i需要的服务时间为ti，1≤i≤n，共有s处提供此服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小。平均等待时间是n个顾客的等待时间(含服务时间)总和除以n。编写一个贪心算法，计算n个顾客的最小平均等待时间及各处的顾客服务次序。
提示：
谈心策略：最短服务时间优先。

输入数据：
第一行，顾客数n及服务处数s，用空格分隔；
第二行开始的n行，每行描述一个顾客，每行两个数，分别是顾客号及他需要的服务时间，用空格分隔。
输出数据
第一行，平均等待时间；
第二行开始的s行，每行描述1处，第1个数为服务处编号，其后为按服务次序先后给出的顾客号，由空格分隔；

算法思想：
算法思想：
该算法使用贪心思想，贪心策略是客户按服务时间长短决定被服务次序，服务时间短的优先被服务，且前往下一个最快能结束服务的服务点
接受服务。
1、定义一个time数组记录每个服务点目前的时间，每服务一个客户time[服务点号]加上该客户的服务时间。
2、随后对每个服务点的目前时间进行比较，数值最小的服务点即为最快能接受服务的服务点，该服务点进行服务，
该客户的等待时间waited_time即为该服务点的目前时间time[服务点号]，并记录好该客户接受服务的服务点号served_point
3、将每个用户的等待时间相加，再除以客户的总数，即得到平均服务时间

头文件代码：
定义了一个类、声明了用到的各个成员变量，公有的service函数是调用贪心算法的入口
MultiService.h:

讯享网

#ifndef MULTISERVICE_H_INCLUDED #define MULTISERVICE_H_INCLUDED #include<iostream> #include<fstream> #include<malloc.h> using namespace std; class MultiService { typedef struct Custom { int number; float service_time; //该客户需要的服务时间 float waited_time; //该客户已经等待的时间 int served_point; //记录该客户被服务的服务处的编号 }Custom ,*Customs; //定义结构体数组，记录一个顾客的编号以及服务时间 Customs customs; int custom_number; //顾客的数量，从文件中读取 int service_number; //服务处的数量，从文件处读取 ofstream fout; void readFile(char *); public: MultiService(char *in ,char *out); ~MultiService() { if(customs) { free(customs); } if(fout) { free(fout); } } void service(); }; #endif // MULTISERVICE_H_INCLUDED 

讯享网输入： 10 2 201 56 128 12 32 1 45 99 109 1000 88 234 69 33 120 55 50 99 48 812

MultiService.cpp:

#include "MultiService.h" void MultiService::readFile(char *in) { ifstream fin(in); if(!fin) { cout<<"File open error!"<<endl; } fin>>custom_number>>service_number; //从文件中读取服务点数量以及客户数量 customs = (Customs)malloc(sizeof(Custom) * custom_number); //申请客户数量个客户的空间 if(!customs) { cout<<"Memory malloc fail!"<<endl; } for(int i = 0 ;i<custom_number ;i++) { fin>>customs[i].number>>customs[i].service_time; //从文件中读入用户的编号以及服务时间 } fin.close(); //关闭文件 } MultiService::MultiService(char *in ,char *out):fout(out) { readFile(in); } void MultiService::service() { for(int i = 0 ;i<custom_number ;i++) //使用选择排序法按每个客户的service_time的大小次序进行排序 { float min = customs[i].service_time; for(int j = i ;j<custom_number ;j++) { if(customs[j].service_time < min) { min = customs[j].service_time; Custom temp = customs[j]; customs[j] = customs[i]; customs[i] = temp; } } } float *time = (float *)malloc(sizeof(int ) * service_number); //申请一个float类型的数组，记录该服务点的当前时间 for(int i = 0 ;i<service_number ;i++) { time[i] = 0; //初始化每个服务点的当前时间 } int left_custom = custom_number; //定义整型left_custom为客户目前的数目 for(int i = 0 ;i<service_number ;i++) //每个服务点开始服务第一个客户 { customs[i].served_point = i; //记录该客户被服务的服务点 time[i] += customs[custom_number - (left_custom--)].service_time; //该服务点的时间++ customs[custom_number - left_custom - 1].waited_time = time[i]; //该用户的等待时间即为该服务点此时的时间 //cout<<"time:"<<time[i]<<endl; } while(left_custom > 0) { int min = time[0]; //找到一个目前时间最短的，即是下一个能够接待客户的服务处 int flag = 0; //记录第几个服务处是下一个最快能接待客户的 for(int i = 1 ;i<service_number ;i++) { if(time[i] < min ) { min = time[i]; flag = i; } } customs[custom_number - left_custom].served_point = flag; //下一个最快能接待客户的服务点接待客户 //并记录客户的服务点 time[flag] += customs[custom_number - (left_custom--)].service_time; //该服务点时间++ customs[custom_number - left_custom -1].waited_time = time[flag]; //该用户的等待时间即为该服务点此时的时间 // cout<<"time["<<flag<<"]:"<<time[flag]<<endl; } float time_sum = 0; for(int i = 0 ;i<service_number ;i++) //输出每个服务点服务的客户编号 { fout<<i + 1<<' '; for(int j = 0 ;j<custom_number ;j++) { if(customs[j].served_point == i) { fout<<customs[j].number<<' '; //把每名顾客的编号输出到文件 } } fout<<endl; } for(int i = 0 ;i<custom_number ;i++) //将总服务时间相加 { //cout<<customs[i].waited_time<<' '; time_sum += customs[i].waited_time; } fout<<time_sum/custom_number; //得到平均服务时间 } 

最后是主函数的调用入口

讯享网#include "MultiService.h" int main() { char *in = "input.txt"; char *out = "output.txt"; MultiService multi_service(in ,out); multi_service.service(); } 

输出到文件中的最后结果为：

1 32 69 201 50 48 2 128 120 45 88 109 340