下次记得弄成UBB代码,否则没人愿意看
by twy847727884 @ 2015-10-15 21:01:41
@[url=/space/show?uid=10342]HY是神[/url] 用堆
by Timothy @ 2015-10-15 21:24:57
@[url=/space/show?uid=10342]HY是神[/url] 每次都要排序一遍,怪不得会炸。还有下次记得用ubb。
by kkksc03 @ 2015-10-16 09:36:29
看看能不能帮助你
```cpp
var n,i,j,k:longint;
a:array[0..100000] of longint;
b:array[0..100000] of int64;
x:int64;
procedure qsort(l,r:integer);
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 l<j then qsort(l,j);if i<r thenqsort(i,r);
end;
begin
readln(n);fillchar(b,sizeof(b),0);
for i:=1 to n do read(a[i]);
qsort(1,n);
b[1]:=a[1]+a[2];i:=3;j:=1;
for k:=2 to n-1 do
begin
if(((j+1)<k) and (b[j+1]<a[i])) or (i>n) then
begin b[k]:=b[j]+b[j+1];inc(j,2);continue;end;
if (((i+1)<=n) and (a[i+1]<b[j]))or (j>k) then
begin b[k]:=a[i]+a[i+1];inc(i,2);continue;end;
b[k]:=a[i]+b[j];
inc(i);inc(j);
end;
for k:=1 to n-1 do x:=x+b[k];
writeln(x);
end.
```
by 格斗家677i @ 2015-11-17 20:49:29
呵呵呵,这道题标算是堆
快排O(n\*n log n)当然不行
by cbx8888 @ 2016-01-10 20:33:52
堆代码:
```cpp
#include<stdio.h>
#include<algorithm>
using namespace std;
int i,j,ans,n,c,k,x;
int a[100005];
int up(int node)
{
int i;
while(node>1)
{
i=node/2;
if(a[node]<a[i])
{
swap(a[node],a[i]);
node=i;
}
else return 0;
}
return 0;
}
int down(int node)
{
int k;
while(node*2<=n)
{
k=node*2;
if((k+1<=n)&&(a[k+1]<a[k])) k++;
if(a[node]>a[k])
{
swap(a[node],a[k]);
node=k;
}
else return 0;
}
}
int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&x);
a[i]=x;
up(i);
}
c=n;
for(i=1;i<c;i++)
{
k=a[1];
swap(a[1],a[n]);
n--;
down(1);
k+=a[1];
swap(a[1],a[n]);
n--;
down(1);
n++;
a[n]=k;
up(n);
ans+=k;
}
printf("%d\n",ans);
return 0;
}
```
by cbx8888 @ 2016-01-10 21:06:30
试试这个:
```cpp
const haha=maxlongint;
var
a,tr:array[0..100000] of longint;
n,i,z,y,x,ans:longint;
function min(a,b:longint):longint;
begin
if a>b then exit(b);
exit(a);
end;
function build(l,r,nod:longint):longint;
begin
if (l=r) then begin tr[nod]:=a[l];exit;end;
build(l,(l+r) div 2,nod+nod);
build((l+r) div 2+1,r,nod+nod+1);
tr[nod]:=min(tr[nod+nod],tr[nod+nod+1]);
end;
function del(p,q:longint):longint;
begin
if (tr[p+p]<>q)and(tr[p+p+1]<>q) then begin tr[p]:=haha;exit(p);end;
if tr[p+p]=q then del:=del(p+p,q)
else del:=del(p+p+1,q);
tr[p]:=min(tr[p+p],tr[p+p+1]);
end;
function insert(p:longint):longint;
begin
if p=0 then exit;
tr[p]:=min(tr[p+p],tr[p+p+1]);
insert(p div 2);
end;
begin
readln(n);
for i:=1 to 10000 do tr[i]:=haha;tr[0]:=-haha;
for i:=1 to n do read(a[i]);
build(1,n,1);
for i:=1 to n-1 do
begin
x:=tr[1];del(1,x);
y:=tr[1];z:=del(1,y);
tr[z]:=x+y;inc(ans,tr[z]);
insert(z div 2);
end;
writeln(ans);
end.
```
by LRM123 @ 2016-01-11 18:31:44
KJKK
by 吴成浩 @ 2016-09-06 12:09:17