#include <cstdio>
#include <algorithm>
int main()
{
int n,w[10001],ans=0;
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&w[i]);
std::sort(w,w+n);
for(int i=0;i<n-1;i++)
{
int x=w[i]+w[i+1];
w[i+1]=x;ans+=x;
for(int j=i+1;j<n-1;j++){
if(w[j]>w[j+1]) {int t=w[j];w[j]=w[j+1];w[j+1]=t;}
else break;}
}
printf("%d",ans);
return 0;
}

测试数据 #0: Accepted, time = 62 ms, mem = 568 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 564 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 568 KiB, score = 10

测试数据 #3: Accepted, time = 15 ms, mem = 568 KiB, score = 10

测试数据 #4: Accepted, time = 15 ms, mem = 572 KiB, score = 10

测试数据 #5: Accepted, time = 15 ms, mem = 572 KiB, score = 10

测试数据 #6: Accepted, time = 46 ms, mem = 572 KiB, score = 10

测试数据 #7: Accepted, time = 62 ms, mem = 564 KiB, score = 10

测试数据 #8: Accepted, time = 62 ms, mem = 572 KiB, score = 10

测试数据 #9: Accepted, time = 62 ms, mem = 572 KiB, score = 10

选择排序也可以很快。。。虽然和插排没什么区别（一开始少排一次。。。）
####c++ code
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int a[20001];
long long ans=0;
int main()
{
int temp;
int jj;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int minn;
for(int g=1;g<n;g++)
for(int i=0;i<=1;i++)
{
minn=1000000000;
for(int j=g+i;j<=n;j++)
if(a[j]<minn)
minn=a[j],jj=j;
temp=a[g+i],a[g+i]=a[jj],a[jj]=temp;
ans+=minn;
if(i==1)
a[g+1]+=a[g];
}

printf("%lld",ans);
system("pause");
return 0;
}

测试数据 #0: Accepted, time = 562 ms, mem = 668 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 668 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 668 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 668 KiB, score = 10
测试数据 #4: Accepted, time = 78 ms, mem = 664 KiB, score = 10
测试数据 #5: Accepted, time = 156 ms, mem = 668 KiB, score = 10
测试数据 #6: Accepted, time = 656 ms, mem = 668 KiB, score = 10
测试数据 #7: Accepted, time = 656 ms, mem = 668 KiB, score = 10
测试数据 #8: Accepted, time = 593 ms, mem = 668 KiB, score = 10
测试数据 #9: Accepted, time = 609 ms, mem = 668 KiB, score = 10
Accepted, time = 3310 ms, mem = 668 KiB, score = 100

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

int a[100010];

unsigned long long ans=0;

int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);

for(int i=1;i<n;i++)
{
sort(a+i,a+n+1);
ans+=a[i]+a[i+1];
a[i+1]+=a[i];
a[i]=0;
}
printf("%lld",ans);
}

加油加油

编译成功

测试数据 #0: Accepted, time = 514 ms, mem = 391672 KiB, score = 10

测试数据 #1: Accepted, time = 452 ms, mem = 391668 KiB, score = 10

测试数据 #2: Accepted, time = 468 ms, mem = 391668 KiB, score = 10

测试数据 #3: Accepted, time = 436 ms, mem = 391668 KiB, score = 10

测试数据 #4: Accepted, time = 530 ms, mem = 391672 KiB, score = 10

测试数据 #5: Accepted, time = 546 ms, mem = 391672 KiB, score = 10

测试数据 #6: Accepted, time = 592 ms, mem = 391672 KiB, score = 10

测试数据 #7: Accepted, time = 405 ms, mem = 391668 KiB, score = 10

测试数据 #8: Accepted, time = 561 ms, mem = 391668 KiB, score = 10

测试数据 #9: Accepted, time = 546 ms, mem = 391668 KiB, score = 10

Accepted, time = 5050 ms, mem = 391672 KiB, score = 100

反人类两亿数组桶排序终于AC了，看正常解法的移步楼下↓↓↓↓↓
#include<bits/stdc++.h>
using namespace std;
long r,n,i,j,mi,s=0,sec=0;
short int a[200000001];
int main(){
cin>>n;
memset(a,0,sizeof(a));
mi=20000;
for (i=1;i<=n;i++){
cin>>r;
a[r]++;
if (r<mi) mi=r;
// if (r>max) max=r;
}
while (n!=1){
if (a[mi]==0){
mi++;
continue;
}
a[mi]--;
sec=mi;
while (a[sec]==0) sec++;
a[sec]--;
s=s+mi+sec;
a[mi+sec]++;
n--;
}

cout<<s;
return 0;
}

测试数据 #0: Accepted, time = 78 ms, mem = 252 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 252 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 252 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 248 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 252 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 248 KiB, score = 10
测试数据 #6: Accepted, time = 62 ms, mem = 252 KiB, score = 10
测试数据 #7: Accepted, time = 62 ms, mem = 252 KiB, score = 10
测试数据 #8: Accepted, time = 62 ms, mem = 248 KiB, score = 10

测试数据 #9: Accepted, time = 62 ms, mem = 248 KiB, score = 10

为何用那些**高端算法**？
一遍快排就行了呀。

最小的两个合并，STL优先队列最方便。

var
n,t,i,j,s,m:longint;
heap:array[1..10000]of longint;

procedure up(k:longint);
begin
while k>1 do
if heap[k shr 1]>heap[k] then
begin
t:=heap[k shr 1];
heap[k shr 1]:=heap[k];
heap[k]:=t;
k:=k shr 1;
end
else break;
end;

procedure down(k:longint);
var temp:longint;
begin
while 2*k<=n do
begin
temp:=k;
if heap[2*k]<heap[temp] then temp:=2*k;
if (heap[2*k+1]<heap[temp])and(2*k+1<=n) then temp:=2*k+1;
if temp=k then break;
t:=heap[temp];
heap[temp]:=heap[k];
heap[k]:=t;
k:=temp;
end;
end;

begin
readln(n);
for i:=1 to n do
begin
read(heap[i]);
up(i);
end;
for i:=1 to n-1 do
begin
m:=0;
m:=m+heap[1];
heap[1]:=heap[n];
n:=n-1;
down(1);
m:=m+heap[1];
heap[1]:=heap[n];
n:=n-1;
down(1);
n:=n+1;
heap[n]:=m;
up(n);
s:=s+m;
end;
write(s);
end

优先队列秒杀

c++ code

#include<cstdio>
#include<queue>
using namespace std;
int main()
{
int n,ans=0,t;
scanf("%d",&n);
priority_queue<int,vector<int>,greater<int> > q;
for (int i=0;i<n;++i) scanf("%d",&t),q.push(t);
for (int i=1;i<n;++i)
{
int a=q.top(); q.pop();
int b=q.top(); q.pop();
ans+=a+b;
q.push(a+b);
}
printf("%d",ans);
return 0;
}

用c++ stl中的优先队列水过
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
priority_queue<int,vector<int>,greater<int> > q;
int n,t,t1,s=0;
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++){
cin>>t;
q.push(t);
}
for(int i=0;i<n-1;i++){
t=q.top();
q.pop();
t1=q.top();
q.pop();
q.push(t1+t);
s+=t1+t;
}
cout<<s;
return 0;
}

一个单调队列的实现，有效的把时间复杂度拉到O（n）（除了sort）
###block code
#include <cstdio>
#include <algorithm>
#define oo 2147483647
using namespace std;
int a[100000],b[100000],ha=1,hb=1;
int ta=0,tb=0;
int ans=0;

int popa()
{
return a[ha++];
}

int popb()
{
return b[hb++];
}

void pushb(int x)
{
ans+=b[++tb]=x;
return;
}

int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
sort(a+1,a+1+n);
ta=n;
for(int i=1;i<n;i++)
{
int sum=0;
for(int j=1;j<3;j++)
{
if(hb>tb)sum+=popa();else if(ha>ta)sum+=popb();
else if(a[ha]<b[hb])sum+=popa();else sum+=popb();
}
pushb(sum);
}
printf("%d",ans);
//fclose(stdin);
//fclose(stdout);
return 0;
}

贪心的算法+堆的数据结构就好啦~

###block code
program ex;
var heap:array[1..10000] of longint;
i,num,n,size,a,b:longint;
ans:int64;
procedure put(x:longint);
var son,fa,t:longint;
begin
inc(size); heap[size]:=x; son:=size;
fa:=son div 2;
while (son<>1) and (heap[fa]>heap[son]) do
begin
t:=heap[fa]; heap[fa]:=heap[son]; heap[son]:=t;
son:=fa; fa:=son div 2;
end;

end;
function get:longint;
var fa,son,t:longint;
begin
get:=heap[1]; heap[1]:=heap[size]; dec(size); fa:=1;
while (fa*2<=size) do
begin
if (fa*2+1>size) or (heap[fa*2]<heap[fa*2+1]) then
son:=fa*2
else
son:=fa*2+1;
if heap[fa]>heap[son] then
begin
t:=heap[fa]; heap[fa]:=heap[son]; heap[son]:=t; fa:=son;
end
else
break;
end;
end;

begin //main
read(n); size:=0; fillchar(heap,sizeof(heap),0); ans:=0;
for i:=1 to n do
begin
read(num); put(num);
end;

while size<>1 do
begin
a:=get; b:=get;
ans:=a+b+ans; a:=a+b; put(a);
end;

write(ans);
end.

var
i,n,nn,x,y,sum,summ,k,xx:longint;
a,b:array[0..10000] of longint;
procedure qsort(l,r:longint);
var
k,x,i,j,t,temp:longint;
begin
i:=l;
j:=r;
k:=(i+j) div 2;
t:=a[k];
repeat
while (t>a[i]) do inc(i);
while (t<a[j]) do dec(j);
if i<=j then
begin
temp:=a[i];
a[i]:=a[j];
a[j]:=temp;
inc(i);
dec(j);
end;
until i>j;
if j>l then qsort(l,j);
if i<r then qsort(i,r);
end;

begin

readln(n);
nn:=n;
fillchar(a,sizeof(a),0);
for i:=1 to n do
read(a[i]);
qsort(1,n);
x:=1;
y:=1;
k:=0;
while (x<=n)or(y<=k) do
begin
if ((a[x]>b[y])and(y<=k)and(k>0))or(x>n) then
begin
sum:=sum+b[y];
inc(y);
end else
begin
sum:=sum+a[x];
inc(x);
end;
inc(xx);
if xx=2 then
begin
xx:=0;
inc(k);
b[k]:=sum;
summ:=summ+sum;
sum:=0;
end;
end;
writeln(summ);
end.

淳朴的方法

#include<iostream>
#include<queue>
using namespace std;
priority_queue<int>q;
main()
{
int n,i,x,a=0,t;
cin>>n;
for(i=0;i<n;i++)
{
cin>>x;
q.push(-x);
}
for(i=1;i<n;i++)
{
t=q.top();
a-=q.top();
q.pop();
t+=q.top();
a-=q.top();
q.pop();
q.push(t);
}
cout<<a;
}

最小堆水题。（新版vijosUI真不错，过题很有快感……）
#include<stdio.h>

void swap(int* a,int* b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}

void minheapify(int* heap,int root,int heapSize)
{
int smallest;
int left=2*root;
int right=2*root+1;
if(left<=heapSize && heap[left]<heap[root])
smallest=left;
else
smallest=root;
if(right<=heapSize && heap[right]<heap[smallest])
smallest=right;
if(smallest!=root)
{
swap(&heap[smallest],&heap[root]);
minheapify(heap,smallest,heapSize);
}
}

void buildHeap(int* heap,int heapSize)
{
int i;
for(i=heapSize/2;i>=1;i--)
minheapify(heap,i,heapSize);
}

int mergefruits(int* heap,int* heapSize)
{
int currentMin;
int result=0;
while(*heapSize!=1)
{
currentMin=heap[1];
heap[1]=heap[*heapSize];
(*heapSize)--;
minheapify(heap,1,(*heapSize));
currentMin+=heap[1];
result+=currentMin;
heap[1]=currentMin;
minheapify(heap,1,(*heapSize));
}
return result;
}

int main()
{
int inputArray[10001];
int i,amount,heapSize;
scanf("%d",&amount);
heapSize=amount;
for(i=1;i<=amount;i++)
scanf("%d",&inputArray[i]);
buildHeap(inputArray,amount);
printf("%d",mergefruits(inputArray,&heapSize));
return 0;
}

用优先队列

评测结果

编译成功

测试数据 #0: Accepted, time = 31 ms, mem = 844 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 556 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 572 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 576 KiB, score = 10

测试数据 #4: Accepted, time = 15 ms, mem = 636 KiB, score = 10

测试数据 #5: Accepted, time = 31 ms, mem = 708 KiB, score = 10

测试数据 #6: Accepted, time = 31 ms, mem = 840 KiB, score = 10

测试数据 #7: Accepted, time = 31 ms, mem = 836 KiB, score = 10

测试数据 #8: Accepted, time = 31 ms, mem = 840 KiB, score = 10

测试数据 #9: Accepted, time = 31 ms, mem = 840 KiB, score = 10

Accepted, time = 201 ms, mem = 844 KiB, score = 100

服务器快就贪心。慢就排序。

ddd

根本就不用排序，其实就是个贪心。
每次找最小的两堆合并就可以啦。

{真不懂某些人只发个代码出来干什么？又没人看，浪费空间}

#include<cstdio>
#include<queue>
using namespace std;
#define IOFileName "P1097"
int n,ai,x,y,ans=0;
priority_queue<int,deque<int>,greater<int> >a;
int main(){
freopen(IOFileName".in","r",stdin);
freopen(IOFileName".out","w",stdout);
scanf("%d\n",&n);
for(int i=0;i<n;i++){
scanf("%d ",&ai);
a.push(ai);
}
while(a.size()>1){
x=a.top();a.pop();
y=a.top();a.pop();
a.push(x+y);
ans+=x+y;
}
printf("%d\n",ans);
}
90MS+276KB

#include<iostream>
#include<iomanip>
#include<string>
#include<algorithm>
#include<ctime>
using namespace std;

int a[10010];
void qsort(int l,int r)
{
int i,j,mid,p;
i=l;
j=r;
mid=a[(l+r)/2];
while(i<=j)
{
while(a[i]<mid) i++;
while(a[j]>mid) j--;
if(i<=j)
{
p=a[i];
a[i]=a[j];
a[j]=p;
i++;
j--;

}

}
if(l<j) qsort(l,j);
if(i<r) qsort(i,r);
}
int main()
{
int n,e=0,y=0;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];

qsort(1,n);
for(int i=2;i<=n;i++)
{
a[i]=a[i]+a[i-1];
e=e+a[i];

int q=a[i];
for(int j=i;j<=n;j++)
{
if(a[j]<=a[i]&&a[j+1]>=a[i]||a[j]<a[i]&&j==n)
{
y=1;
for(int o=i;o<=j-1;o++)
{
a[o]=a[o+1];

}
a[j]=q;
}

if(y==1) break;

}

y=0;
}
cout<<e;

return 0;

}