18844561135 2018-02-23 15:39:07
点我顶贴
收藏
删除
//抽取两个最小值,序号较大的一个由后面的数据覆盖,选取最小值的循环次数减少,逐次合并至没有循环
#include<iostream>
#include<cmath>
using namespace std;
#define N 100000000
int main()
{
long i,j,a[10000],n,min[2][2]={{N,N},{N,N}},pwr=0;
cin>>n;
for(i=0;i<n;i++) cin>>a[i];
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i;j++)
{
if(a[j]<min[0][1]&&a[j]!=-1)
{
min[0][0]=j;
min[0][1]=a[j];
}
}
for(j=0;j<n-i;j++)
{
if(a[j]<min[1][1]&&j!=min[0][0]&&a[j]!=-1)
{
min[1][0]=j;
min[1][1]=a[j];
}
}
if(min[0][0]<min[1][0])
{
a[min[0][0]]+=a[min[1][0]];
pwr+=a[min[0][0]];
for(j=min[1][0];j<n-i;j++) a[j]=a[j+1];
}
else
{
a[min[1][0]]+=a[min[0][0]];
pwr+=a[min[1][0]];
for(j=min[0][0];j<n-i;j++) a[j]=a[j+1];
}
min[0][1]=N;
min[1][1]=N;
}
cout<<pwr;
return 0;
}