我是始终合并最小的两堆 结果只有10分 还超时 排序用的快排

program mars；

var

i,j,n,tem,k,best:longint；

a:array[1..10001] of integer；

procedure sort(s,t:longint)；//快排

var

i,j,tem,r,x:integer；

begin

r:=random(t-s+1)+s；

i:=s； j:=t； x:=a[i]；

repeat

while (i<j) and (x<a[j]) do dec(j)；

if i<j then begin a[i]:=a[j]； inc(i)； end；

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

if i<j then begin a[j]:=a[i]； dec(j)； end；

until i=j；

a[i]:=x； dec(j)； inc(i)；

if i<t then sort(i,t)；

if s<j then sort(s,j)；

end；

begin

randomize；

readln(n)；

for i:=1 to n do read(a[i])；

sort(1,n)；//快排

best:=0；//记录最小值

i:=1；

for i:=1 to n-1 do begin

j:=i+1；

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

a[i+1]:=a[i]+a[i+1]；//得到新的果子数

tem:=a[i+1]；

while a[j+1]<tem do j:=j+1；//查找新的堆数应处的位置

for k:=i+1 to j-1 do a[k]:=a[k+1]；//把其位置前的数全部前移

a[j]:=tem；//给其应在位置赋值

end；

writeln(best)；

end.

前段时间我问过这道题

有人说我思想有问题

但是谁能不能举出反例

n=10000

快排的时间复杂度是n*log(n)

要调用9999次快排

超时是一定的了

在vijos上我用链表写过了 这里不行

后来改用 双递增队列才过的

是有问题的。。。但是我一下子忘了。。。

把新加的元素进行插入排序即可.

合并果子提倡dp，不过一开始也是从快排加插入过的。

把新加的元素进行插入排序即可.

合并果子提倡dp，不过一开始也是从快排加插入过的。

我是第一次用的快排

而后面是是寻找他的位置

然后插入

超时有2个点

而大多数都出错~