1319：【例6.1】排隊接水

時間限制: 1000 ms ??? ??? 內存限制: 65536 KB
提交數: 17332 ??? 通過數: 7890

【題目描述】

有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

【分析】

? ? ? ? 由干排隊時，越靠前面的計算次數越多，因此越小的排在越前面得出的結果越小（可以
（可用數學方法簡單證明，這里就不再贅述），所以這道題可以用貪心法解答，基本步驟為∶
（1）將輸入的時間按從小到大排序;（2）將排序后的時間按順序依次放入每個水龍頭的隊列中;（3）統計，輸出答案。

【參考代碼】

#include <stdio.h> #define N 1010struct node {int time; //接水時間 int site; //位置 }a[N],t;int main() {int n,i,j;double sum=0;scanf("%d",&n);for(i=0;i<n;i++){scanf("%d",&a[i].time);a[i].site=i;}for(i=0;i<n-1;i++) //比較排序 {for(j=i+1;j<n;j++){if(a[i].time > a[j].time){t=a[i];a[i]=a[j];a[j]=t;}}}for(i=0;i<n;i++)printf("%d ",a[i].site+1);printf("\n");for(i=0;i<n;++i)sum+=a[i].time*(n-1-i);printf("%.2lf\n",sum*1.0/n);return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1319

新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的信息学奥赛一本通（1319：【例6.1】排队接水）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。