我用贪心做的，先冒泡，再插入排序，top始终指向最小的一堆。

可……为什么只有10分呢？总的来说，结果比标准输出大一点……

program p25(input,output);

var zs,a,b,n,i,top,c:longint;

ab:array [1..10000] of longint;

procedure px;

var xx:longint;

begin

for xx:=top to n do

if ab[xx]>ab[xx+1]

then begin

c:=ab[xx];

ab[xx]:=ab[xx+1];

ab[xx+1]:=c;

end

else break;

end;

begin

readln(n);

for i:=1 to n do

read(ab[i]);

for a:=1 to n do

for b:=a+1 to n do

if ab[a]>ab[b]

then begin

c:=ab[a];

ab[a]:=ab[b];

ab[b]:=c;

end;

top:=1;

zs:=0;

while top<n do

begin

ab[top+1]:=ab[top+1]+ab[top];

zs:=zs+ab[top+1];

top:=top+1;

px;

end;

writeln(zs);

end.

回复 楼主hc199581 的帖子

LZ啊。。就算你的程序写对了也会TLE的。。

此题正解：小根堆维护 OR 快排+双单调队列维护

Code：

PS.这个程序不是我写的，是我很久以前抄的别人的代码。。。= =，是小根堆维护的

#include <iostream>

using namespace std;

int a[10001],b[10001];

int n;

void work(int low,int high)

{

int i=low,j=low*2,k=a[i];

while(j<=high)

{

if(j<high && a[j]>a[j+1])

j++;

if(k>a[j])

{

a[i]=a[j];

i=j;

j=i*2;

}

else

break;

}

a[i]=k;

}

int main(void)

{

int i;

int ans=0,tmp,now;

cin>>n;

for (i=1;i<=n;i++) cin>>a[i];

for (i=n/2;i>=1;i--)

work(i,n);

for (i=n;i>1;i--)

{

tmp=a[1];

a[1]=a[i];

a[i]=tmp;

work(1,i-1);

ans=ans+tmp+a[1];

a[1]+=tmp;

work(1,i-1);

}

cout<<ans<<endl;

return 0;

}

- -

冒泡就直接爆了...还插入排序...

但是，可以证明出这个算法是错的吗？

还有，我用的是PASCAL……

冒泡排序和插入排序的时间复杂度都是O(n*n) 会爆时间....

应该是快速排序+二分查找 或者是堆排序

堆排和快排时间复杂度差不多啦，都可以用

不用排序，只要建立小根堆，然后比较

min为min{heap[2]，heap[3]}的下标,

inc(heap[1],heap[min]);

inc(ans,heap[1]);

heap[min]:=maxint;

down(min);

down(1);

重复n-1次就OK~