讨论 / 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;

}

#1 Jabbar@2019-06-23 17:15:58
回复 删除
#include<bits/stdc++.h>

using namespace std;

int a[100000];

int main(){

int n,sum=0;

cin>>n;

for(int i=1;i<=n;i++)

{

cin>>a[i];

}

sort(a+1,a+n+1);

while(1){

int j=1;

while(a[j]==0)

j++;

if(j==n) break;

else {

a[j]+=a[j+1];

sum+=a[j];

for(int l=j+1;l<n;l++)

{

a[l]=a[l+1];

}

n--;

}

for(int l=j;l<n;l++)

{

if(a[l]>a[l+1])

{

swap(a[l],a[l+1]);

}

}

}

cout<<sum;

return 0;

}

#2 Jabbar@2019-06-23 17:16:06
回复 删除
垃圾

#3 bfw@2019-08-22 17:11:25
回复 删除
这题用优先队列写15行解决
#4 bfw@2019-08-22 17:11:31
回复 删除
而且不压行
查看更多回复
提交回复