【寒假任务】洛谷1223 排队接水

2019-11-14 11:35:43

字体：大中小

来源：转载

供稿：网友

问题描述 有n个人在一个水龙头前排队接水，编号为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 算法讨论 贪心，让每个人的等待时间都最少即可。时间复杂度O(n log n)。

const maxn=1000;var a:array[1..maxn,1..2] of longint; i,j,n:longint; s,ans:real;PRocedure qsort(l,r:longint);var i,j,m,t:longint;begin i:=l; j:=r; m:=a[(l+r) div 2,1]; repeat while a[i,1]<m do inc(i); while a[j,1]>m do dec(j); if i<=j then begin t:=a[i,1]; a[i,1]:=a[j,1]; a[j,1]:=t; t:=a[i,2]; a[i,2]:=a[j,2]; a[j,2]:=t; inc(i); dec(j) end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r)end;begin read(n); for i:=1 to n do begin read(a[i,1]); a[i,2]:=i end; qsort(1,n); for i:=1 to n-1 do begin write(a[i,2],' '); s:=s+a[i,1]; ans:=ans+s end; write(a[n,2]); ans:=ans/n; writeln; write(ans:0:2)end.

这里写图片描述 Pixiv ID：56201975