#include<algorithm>
using namespace std;
int main()
{
int n,a[10001]={0};
cin >> n ;
for(int i=1;i<=n;++i) cin >> a[i] ;
for(int i=2;i<=n;++i)
{
sort(a,a+n+1);
a[i]+=a[(i-1)];a[(i-1)]=0;
}
cout << a[n] ;
return 0;
}
这样也过不了,怎么改进?
#include<iostream>
#include<stdio.h>
#include<memory>
#include<stdlib.h>
#include<string.h>
using namespace std;
int a[10001],b[20005];
int main()
{
int i,j,left,right,sum=0;
int n;
cin>>n;
for (i=1;i<=n;i++)
{
cin>>a[i];
b[a[i]]++;
}
int k=0;
for (i=1;i<=20000;i++)
{
for (j=1;j<=b[i];j++)
{
a[++k]=i;
}
}
for (i=1;i<n;i++)
{
a[i]=a[i]+a[i+1];
sum+=a[i];
for (j=i+1;j<=n-1;j++)
{
if (a[j+1]>=a[i]) break;
a[j]=a[j+1];
}
a[j]=a[i];
}
cout<<sum;
return 0;
}
[color=green]//这是插入排序,复杂度比你反而低。每次你所改变的只有一个数,发现了么?把这个数插入进去就行了。
//还有一种方法是归并
program p20;
var
i,j,m:longint;
a,b,c:array[1..100]of longint;
begin
for i:=1 to 7 do
begin
readln(a[i],b[i]);
c[i]:=a[i]+b[i];
end;
for i:=1 to 7 do
if c[i]>m then
begin
m:=c[i];
j:=i;
end;
write(j);
end.