心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0

简单的贪心,用堆优化。

以下是我的代码:

#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 阅读(454) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理