題目鏈接：
http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1184
早起一水
Time Limit: 1000 MS Memory Limit: 65535 K
Total Submit: 645(172 users) Total Accepted: 202(157 users) Rating: Special Judge: No
Description
n個(gè)人排隊(duì)接水，編號(hào)為1到n，每個(gè)人的接水時(shí)間為Ti，請(qǐng)編程找出這n個(gè)人的排隊(duì)序列（接水時(shí)間的一樣的按照他們的編號(hào)排隊(duì)），使得他們的平均等待接水時(shí)間最小。

1 <= n <= 100000。

0 <= Ti <= 200000。

Input
有多組測(cè)試數(shù)據(jù)。

對(duì)于每組測(cè)試數(shù)據(jù)，第一行為n，表示有n個(gè)人。第二行為n個(gè)數(shù)Ti， 表示第i個(gè)人的接水時(shí)間。

Output
輸出共兩行。

第一行輸出n個(gè)人的排隊(duì)序列，每兩個(gè)數(shù)之間有一個(gè)空格。

第二行為這種排隊(duì)序列下的最小平均等待時(shí)間，保留到小數(shù)點(diǎn)后兩位。

Sample Input
10
56 12 1 99 1000 234 33 55 99 812
4
1 1 1 1
Sample Output
3 2 7 8 1 4 9 6 10 5
291.90
1 2 3 4
1.50

很簡單，就是先給每個(gè)接水的人排上序號(hào)，然后sort一下就可以了，然后再從前往后開始計(jì)算就可以了，注意第一個(gè)人等待的接水時(shí)間為0。
下面是AC代碼：

#include<cstdio> #include<cstring> #include<algorithm> using namespace std;struct node {int id,t; }a[100005];bool cmp(node x,node y) {if(x.t==y.t){return x.id<y.id;}return x.t<y.t; } int main() {int n;while(~scanf("%d",&n)){for(int i=0;i<n;i++){a[i].id=i+1;scanf("%d",&a[i].t);}sort(a,a+n,cmp);for(int i=0;i<n-1;i++){printf("%d ",a[i].id);}printf("%d\n",a[n-1].id);double sum=a[0].t,ans=0;for(int i=1;i<n;i++){ans=ans+sum;sum+=a[i].t;}printf("%.2lf\n",double(ans)/double(n));}return 0; }

總結(jié)

以上是生活随笔為你收集整理的哈理工OJ 1184 早起一水（水题）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。