讨论 / AC,这个题是要用排序才比较快吗?这个算法有什么不妥么?新人求指点
18844561135 2018-02-22 23: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 02: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 02:16:06
回复 删除
垃圾

#3 bfw@2019-08-22 02:11:25
回复 删除
这题用优先队列写15行解决
#4 bfw@2019-08-22 02:11:31
回复 删除
而且不压行
#5 g71d98@2022-02-09 04:45:24
回复 删除
#include<iostream>

using namespace std;

int main()

{

int n; cin >> n; int arr[10000]={0};

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

{

cin >> arr[i];

}

int temp = 0;

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

{

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

{

if (arr[i] > arr[j]) { temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }

}

}

int sum = 0;

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

{

if (i == 0) sum = (n - 1) * arr[i];

else sum = sum + (n - i) * arr[i];

}

cout << sum;

return 0;

}

#6 橙紫爱MC@2022-02-12 22:49:41
回复 删除
回复 #2 Jabbar::D你最牛B行不行?
查看更多回复
提交回复