排队接水
|
源程序名 water.???（pas, c, cpp）
可执行文件名 water.exe
输入文件名 water.in
输出文件名 water.out |
【问题描述】
有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。
【输入】
输入文件共两行，第一行为n；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。
【输出】
输出文件有两行，第一行为一种排队顺序，即1到n的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。
【样例】
water.in water.out
10 3 2 7 8 1 4 9 6 10 5
56 12 1 99 1000 234 33 55 99 812 532.00(改之前：291.90)
【算法分析】
平均等待时间是每个人的等待时间之和再除以n，因为n是一个常数，所以等待时间之和最小，也就是平均等待时间最小。假设是按照1~n的自然顺序排列的，则这个问题就是求以下公式的最小值：
如果用穷举的方法求解，就需要我们产生n个人的所有不同排列，然后计算每种排列所需要等待的时间之和，再“打擂台”得到最小值，但这种方法需要进行n!次求和以及判断，时间复杂度很差！
其实，我们认真研究一下上面的公式，发现可以改写成如下形式：
这个公式何时取最小值呢？对于任意一种排列k1, k2, k3, …, kn，当≤≤≤…≤时，total取到最小值。如何证明呢？方法如下：
因为
假设i<j，而<，这时的和为total1，而把ki和kj互换位置，设新的和为total2，则：
我们发现上述△total恒大于0，所以也说明了任何次序的改变，都会导致等待时间的增加。从而证明了我们的设想。
既然如此，我们就得到了一种最贪心的策略：把接水时间少的人尽可能排在前面。这样一来，问题的本质就变成：把n个等待时间按非递减顺序排列，输出这种排列，并求出这种排列下的平均等待时间。
C语言代码：
＃i nclude <stdio.h>
#define N 100/*假设最大数据量为100*/
int main()
{
int T[N],/*接受输入数据*/
sort[N],/*记录排序前的位置*/
n=0,/*数据个数*/
i,j,/*循环量*/
time=0,/*总等待时间*/
count=0;/*记录个数*/
FILE *in,*out;
in=fopen("water.in","r");
/*输入*/
fscanf(in,"%d",&n);
for(i=0;i<n;i++)
{
fscanf(in,"%d",&T[i]);
}
/*初始化，开始所记录的位置为-1*/
for(i=0;i<n;i++)
{
sort[i]=-1;
}
/*sort排序*/
for(i=0;i<n;i++)
{
count=0;
for(j=0;j<n;j++)
{
if(T[i]>T[j])count++;/*记录比T[i]小的数的个数*/
}
while(sort[count]!=-1)count++;/*注意有相同的数的情况，则位置要相应后移*/
sort[count]=i;/*记录T[i]在sort的位置*/
}
for(i=0;i<n;i++)
{
time+=(n-i)*T[sort[i]];/*累加等待时间*/
}
/*输出*/
out=fopen("water.out","w");
fprintf(out,"%d",sort[0]+1);
for(i=1;i<n;i++)
{
fprintf(out," %d",sort[i]+1);
}
fprintf(out,"\n%.2f",time*1.0/n);
fclose(in);
fclose(out);
}
