讨论 / AC,这个题是要用排序才比较快吗?这个算法有什么不妥么?新人求指点
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;

}

查看更多回复
提交回复