題目描述

有n個人在一個水龍頭前排隊接水，假如每個人接水的時間為Ti，請編程找出這n個人排隊的一種順序，使得n個人的平均等待時間最小。

輸入輸出格式

輸入格式：

輸入共兩行，第一行為n；第二行分別表示第1個人到第n個人每人的接水時間T1，T2，…，Tn，每個數據之間有1個空格。

輸出格式：

輸出有兩行，第一行為一種排隊順序，即1到n的一種排列；第二行為這種排列方案下的平均等待時間(輸出結果精確到小數點后兩位)。

輸入輸出樣例

輸入樣例#1：

10?
56 12 1 99 1000 234 33 55 99 812

輸出樣例#1：

3 2 7 8 1 4 9 6 10 5
291.90

思路：對于每一個人，在場剩余每個人都要經歷一次他的打水時間。故遍歷整個數組求其他人在這個人打水時花費的總時間累加到sum上，最后sum除以n。

源代碼

#include<iostream> #include<algorithm> #include<iomanip> using namespace std; struct people{//結構體int num;int time; }arr[5000]; bool cmp(people a,people b){//排序因子return a.time<b.time;//按時間升序 } int main() {int n;int i;double time_sum=0,time_average;cin>>n;for(i=1;i<=n;i++) {cin>>arr[i].time;arr[i].num=i;}sort(arr+1,arr+1+n,cmp);//升序排序for(i=1;i<=n;i++) {cout<<arr[i].num<<" ";if(n-i>=1) time_sum+=arr[i].time*(n-i);//計算總時間} time_average=time_sum/n;//計算平均時間cout<<endl;cout<<setiosflags(ios::fixed)<<setprecision(2);cout<<time_average<<endl;return 0; }

?

總結

以上是生活随笔為你收集整理的排队接水（洛谷-P1223）的全部內容，希望文章能夠幫你解決所遇到的問題。

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