簡單的貪心，用堆優化。
以下是我的代碼：
#include<stdio.h>
long a[10001],n,sum;
void read()
{
long i;
scanf("%ld",&n);
for(i=1;i<=n;i++)
scanf("%ld",&a[i]);
}
void adjust(long a[],long begin,long end)
{
long i,m;
m=a[begin];
for(i=begin*2;i<=end;i*=2)
{
if(i<end && a[i]>a[i+1])
i++;
if(m<=a[i])
break;
a[begin]=a[i];
begin=i;
}
a[begin]=m;
}
void hsort(long a[],long n)
{
long i,t;
for(i=n/2;i>=1;i--)
adjust(a,i,n);
}
void solve()
{
long i,j;
sum=0;
for(i=n;i>=2;i--)
{
j=2;
if( i>2 && a[j]>a[j+1] )
j++;
sum+=a[1]+a[j];
a[j]+=a[1];
a[1]=a[i];
adjust(a,j,i-1);
adjust(a,1,i-1);
}
}
void write()
{
printf("%ld\n",sum);
}
int main()
{
read();
hsort(a,n);
solve();
write();
return 0;
}
posted on 2010-01-06 18:52
lee1r 閱讀(475)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數據結構