wait.cpp

对于给定的n个顾客需要的服务时间

#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
int Max(int a[],int n)
{
	int pos=0;
	for(int i=0;i<n;i++)
		if(a[pos]<a[i])
			pos=i;
		return pos;
}
void Swap(int &x,int &y)
{
	int temp;
	temp=x;x=y;y=temp;
}
void Selectsort(int a[],int n)
{
	for(int size=n;size>1;size--)
	{
		int j=Max(a,size);
		Swap(a[j],a[size-1]);
	}
}
int Partition(int a[],int p,int r)
{
	int i=p,j=r+1,x=a[p];
	while(true)
	{
		while(a[++i]<x&&i<=r);
		while(a[--j]>x);
		if(i>=j)break;
		Swap(a[i],a[j]);
	}
	a[p]=a[j];
	a[j]=x;
	return j;
}
void Quicksort(int a[],int p,int r)
{	if(r-p<=9)
		Selectsort(&a[p],r-p+1);
	else if(p<r)
	{
		int q=Partition(a,p,r);
		Quicksort(a,p,q-1);
		Quicksort(a,q+1,r);
	}
}
void main()
{
	if(in.fail())
	{
		cout<<"the input.txt is not exist!";
		exit(1);
	}
	int n;
	in>>n;
	int *a=new int [n];
	for(int i=0;i<n;i++)
	{
		in>>a[i];
	}
	Quicksort(a,0,n-1);
	double num=0;
	for(i=0;i<n;i++)
		num+=a[i]*(n-i);
	num=num/n;
	out<<setiosflags(ios::fixed);
	out<<setprecision(2)<<num<<endl;
}