問題描述 有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 算法討論 貪心，讓每個人的等待時間都最少即可。時間復(fù)雜度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
新聞熱點(diǎn)
疑難解答
