多处最优服务问题final

1、算法实现题4-7 多处最优服务次序问题 问题描述：设有n 个顾客同时等待一项服务。顾客i需要的服务时间为ti, 1i n 。共有s处可以提供此服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?平均等待时间是n 个顾客等待服务时间的总和除以n。编程任务：对于给定的n个顾客需要的服务时间和s的值，编程计算最优服务次序。数据输入：由文件input.txt给出输入数据。第一行有2 个正整数n 和s，表示有n 个顾客且有s 处可以提供顾客需要的服务。接下来的1 行中，有n个正整数，表示n个顾客需要的服务时间。结果输出:将编程计算出的最小平均等待时间输出到文件output.txt。输入示例in

2、put.txt10 256 12 1 99 1000 234 33 55 99 812输出示例output.txt336#include #include using namespace std;typedef struct Jobint ID;int time;Job;typedef struct JobNodeint ID;int time;JobNode *next;JobNode,*pJobNode;typedef struct Headerint s;JobNode *next;Header,pHeader;int main()void QuickSort(Job *job,int

3、left,int right);void outSort(Job *job,int n);void display(Header *M,int m,int n);void solve(Header *head,Job *job,int n,int m);int m,n;coutttn;coutm;Header *head= new Headerm;cout n;Job *job = new Jobn;coutn请按序号输入每个作业调度需要的时间:;for(int i=0;ijobi.time;jobi.ID=i;QuickSort(job,0,n-1);outSort(job,n);solve

4、(head,job,n,m);display(head,m,n);coutendlendl;return 0;int SelectMin(Header *M,int m)int k=0;for(int i=1;im;i+)if(Mi.sMk.s)k=i;return k;void QuickSort(Job *job,int left,int right)int middle=0,i=left,j=right;Job itemp;middle=job(left+right)/2.time;dowhile(jobi.timemiddle)&(imiddle)&(jleft) j-;if(i=j)

5、itemp = jobj;jobj = jobi;jobi = itemp;i+;j-;while(i=j);if(lefti) QuickSort(job,i,right);void display(Header *M,int m,int n)int *total = new intm;int *current= new intm;for(int j=0;jm;j+)totalj=0;for(j=0;jm;j+)currentj=0;double average=0;JobNode *p;for(int i=0;im;i+)coutn第i台机器上处理的工作序号:;if(Mi.next = 0

6、)continue;p=Mi.next;docoutIDtime;totali=totali+currenti;/cout(totalinext;while(p!=0);coutendl;for(j=0;jm;j+)average+=totalj;cout平均时间：average/n;void outSort(Job *job,int n)coutn按工作时间由小到大为:n时间:t;for(int i=0;in;i+)coutsetw(4)jobi.time;coutn序号:t;for(i=0;in;i+)coutsetw(4)jobi.ID;void solve(Header *head,J

7、ob *job,int n,int m)int k;for (int i=0;im&itime = jobi.time;jobnode-ID = jobi.ID;jobnode-next= 0;headi.s = jobnode-time;headi.next=jobnode;if(i=m)for(i;im)for(i;itime = jobi.time;jobnode-ID = jobi.ID;jobnode-next = 0;k = SelectMin(head,m);p = headk.next;headk.s += jobnode-time;while(p-next!=0)p=p-next;p-next=jobnode;(注解:很多人会对这道题中平均等待服务时间不理解,下面我解释一下变做出这道题的具体运算过程.一个顾客的等待服务时间是顾客的等待时间加上这个顾客的服务时间,学过操作系统的同学应该明白进程的周转时间吧, 说的好像只有顾客的等待时间而没有服务时间，这也是悲催的原因吧。下面说下此程序的运算过程：11125131510013041899035345699812Total0=total+current0Current0=current0+812Total0=total+current0Current0=current0+99Tot