machinegreedy实验4_7.cpp

最优服务次序问题 问题描述: 设有n 个顾客同时等待一项服务。顾客i需要的服务时间为t(i),i=1,…,n 。...个顾客等待服务时间的 总和除以n。 编程任务: 对于给定的n个顾客需要的服务时间,

//实验4-7多处最优服务次序问题，求最小平均等待时间
//该算法注意的是自身的服务时间也必须加入等待时间，例如顾客1服务时间是8，则他的等待时间为8

#include <stdio.h>
#include<iostream.h>
#include<vector>
#include<algorithm>

double greedy(int x[],int s, int n);   //为作业分配机器
void sort(int[], int);

void main()
{
	int n=0, m=0, s=0;  //n顾客数量 s机器数量
	int x[50];          //存放顾客需要的服务时间

	while(true){
		cout<<"*****多处最优服务次序问题，求最小平均等待时间*****"<<endl;
		cout<<endl;
		cout<<"请输入等待服务的顾客数量(n): "<<endl;
		cin>>n;
		cout<<"请输入提供服务的机器数量(s): "<<endl;
		cin>>s;
		cout<<endl;
		cout<<"请输入每个顾客的服务时间: "<<endl;
		for(m=0; m<n; m++)   //该循环中只能输入个数刚好是顾客的数量n
		{
			int time = 0;     
			cin>>time;
			x[m] = time;
		}
		double avg=greedy(x, s, n);   //求最小平均等待时间
		cout<<"排好序的服务时间为： "<<endl;
		for(int i=0; i<n; i++)
			cout<<x[i]<<" ";
		cout<<endl;
		cout<<"平均等待时间为:  "<<avg<<endl;
		cout<<endl;
		}
	
}
double greedy(int x[],int s, int n)   
{  
 
	int *st = new int[s+1];        //用来统计等待的服务时间
      for(int q=0;q<s+1;q++)
			st[q]=0;
	int *su = new int[s+1];        //辅助数组
	for(int q1=0;q1<s+1;q1++)
		su[q1]=0;
    
	sort(x, n);						//将X数组升序排序
	int i=0,j=0;
	while(i<n)
	{
		st[j]+=x[i];				//将排好序的服务时间序列分别加在服务器上
		su[j]+=st[j];				//su数组用来记录每个服务机器上的服务等待时间
		i++;j++;
		if(j==s)
		j=0;
	}
	double t=0;
	for(i=0;i<s;i++)
	t+=su[i];
    return t/n;
}
void sort(int x[], int n)   //将数组即输入的服务时间排序，按升序排，采用冒泡排序
{
	for(int i=0;i<n;i++) 
		for(int j=0;j<n-i-1;j++) 
			if(x[j]>x[j+1]) 
			{ 
				int k=x[j];
				x[j]=x[j+1];
				x[j+1]=k; 
			} 
}