Greedy

每做一次加總 就做一次排列 拿最小的相加

最下面的程式碼為4XXms (因為多餘的指令  造成1.2秒)

/********1.2S的作法 太慢了*********************************/

#include<stdio.h>
#include<stdlib.h>
main()
{
 int n,m;
 while(scanf("%d",&n)==1&&n!=0)
   {
    int number[100001]={0},mm=n,time=0;
     while(n--)
       {
        scanf("%d",&m);
        number[m]++;
       }
    long long int line[100001]={0};
    int a,b,c,top=0;
    for(a=1;a<=100000;a++)
     if(number[a]!=0)
      for(b=0;b<number[a];b++)
       {line[top]=a;top++;}
    long long int ans=0,sum,temp;
    mm=top ;
    for(a=0;a<mm-1;a++)
     {
      sum=line[a+1]+line[a];
      ans+=sum;
      line[a+1]+=line[a];
       for(b=a+1;b<mm-1;b++)
        if(line[b]>line[b+1]) {temp=line[b+1];line[b+1]=line[b];line[b]=temp;}
        else break;
     }
     printf("%lld\n",ans);
   }
 return 0;
}

/******************************************************/

#include<stdio.h>
#include<stdlib.h>
main()
{
 int n,m;
 while(scanf("%d",&n)==1&&n!=0)
   {
    int number[100001]={0},m,a,b,c;
    long long int line[5001],top=0;
     for(a=0;a<n;a++)
         {
            scanf("%d",&m);
            number[m]++;
          }
    for(a=1;a<=100000;a++)
         for(b=0;b<number[a];b++)
             line[top++]=a;
    long long int sum=0,temp;
    for(a=1;a<n;a++)
       {
          int data=line[a-1]+line[a];
          sum=sum+data;
            for(b=a+1;b<n;b++)
                 if(line[b]<data)
                   line[b-1]=line[b];
                 else break;
          line[b-1]=data;
     }
     printf("%lld\n",sum);
   }
 return 0;
}