题目描述 Description
输入描述 Input
Description
输出描述 Output
Description
输出包括一行,这一行只包含一个整数,也就是最小的体力耗费值。输入数据保证这个值小于231。
样例输入 Sample
Input
3
1 2 9
样例输出 Sample
Output
15
数据范围及提示 Data Size &
Hint
对于30%的数据,保证有n<=1000:
对于50%的数据,保证有n<=5000;
对于全部的数据,保证有n<=10000。
分类标签 Tags 点此展开
基本思路:
始终从当前的所有果子堆中取出最小的两个合并,加上那个体力,
合并后的果子再排序,然后再找最小的两个果子堆合并。
代码:
#include<
cstdio >
#include<
iostream >
using namespace
std;
int
n,w[10020];
int get();int
size=0;
void put(int
k);
void
input()
{
scanf("%d",&n);
for(int
i=1;i<=n;++i)
{
scanf("%d",&k);
put(k);
}
}
void put(int
k)
{
++size;
w[size]=k;
int
now=size,next;
while(now>1)
{
next=now/2;
if(w[now]>=w[next]) return;
swap(w[now],w[next]);
now=next;
}
}
int get()
{
int
res=w[1];
w[1]=w[size--];
int
now=1,next;
while(2*now<=size)
{
next=2*now;
if(next+1<=size&&w[next+1]
if(w[now]<=w[next]) return res;
swap(w[now],w[next]);
now=next;
}
return res;
}
int main()
{
input();
int sum=0;
for(int
i=1;i<=n-1;++i)
{
int
m=get()+get();
sum+=m;
put(m);
}
cout<<sum;
return 0;
}