测评机： Xeond[6]

得分： 80分

提交日期： 2008-11-2 7:09:00

有效耗时： 4110毫秒

测试结果1: 通过本测试点|有效耗时172:ms

测试结果2: 通过本测试点|有效耗时172:ms

测试结果3: 通过本测试点|有效耗时172:ms

测试结果4: 通过本测试点|有效耗时313:ms

测试结果5: 通过本测试点|有效耗时375:ms

测试结果6: 通过本测试点|有效耗时937:ms

测试结果7: 选手程序运行超过时限

测试结果8: 通过本测试点|有效耗时953:ms

测试结果9: 通过本测试点|有效耗时1016:ms

测试结果10: 选手程序运行超过时限

思路是先快排,然后合并最小的果子,之后用插入.再把最小的两堆合并.

下面是程序:

(还可以优化吗?)

var

a:array[0..100000] of longint；

i,j,k,l,n:longint；

procedure quick(l,r:longint)；

var

i,j,x,y:longint；

begin

i:=l；j:=r；

x:=a[(i+j) div 2]；

repeat

while a[i]<x do inc(i)；

while a[j]>x do dec(j)；

if i<=j then

begin

y:=a[i]；

a[i]:=a[j]；

a[j]:=y；

inc(i)；

dec(j)；

end；

until i>j；

if i<r then quick(i,r)；

if j>l then quick(l,j)；

end；

procedure cr；

var

i,j,x:longint；

begin

a[0]:=-maxlongint；

for i:=2 to n do

begin

j:=i-1；

x:=a[i]；

while x<a[j] do

begin

a[j+1]:=a[j]；

dec(j)；

end；

a[j+1]:=x；

end；

end；

begin

readln(n)；

for i:=1 to n do

read(a[i])；

quick(1,n)；

while n<>1 do

begin

a[2]:=a[1]+a[2]；

for i:=1 to n-1 do

a[i]:=a[i+1]；

k:=k+a[1]；

dec(n)；

cr；

end；

writeln(k)；

end.