当前位置 博文首页 > Deco00ffcc的博客：排队打水问题（一个水龙头，需计算平均等待时
排队接水 （water.cpp/.in/.out）
【题目描述】
有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。
【输入】
共两行，第一行为n(1≤n≤1000)；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。
【输出】
有两行，第一行为一种排队顺序，即1到n的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。
【输入样例】
10?????????? ?????????????? ?????????????? ?????????????? ?????????????? ?????????????? ??????????????
56 12 1 99 1000 234 33 55 99 812
【输出样例】
3 2 7 8 1 4 9 6 10 5
291.90
这道题大多数人使用了贪心算法，但是对于初学者，我这里有一个看起来没有那么高深的代码，虽然答案可能比较繁琐。也是文件版本的，有用的话改一下就行。
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("water.in","r",stdin);
freopen("water.out","w",stdout);
int n,a[10001],b[10001],st,c[10001];
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
c[i]=a[i];
}
for(int j=1;j<=n;j++)
{
int mini=1001;
for(int i=1;i<=n;i++)
{
if(a[i]<mini)
{
mini=a[i];
st=i;
}
}
b[j]=st;
a[st]=1002;
}
for (int i=1;i<=n;i++)
{
cout<<b[i]<<" ";
}
float sum=0;
for(int i=1;i<=n;i++)
{
sum=sum+(n-i)*c[b[i]];
}
float gong;
gong=sum/n;
printf("%.2f",gong);
fclose(stdin);fclose(stdout);
return 0;
}
