摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法:Greedy
1.每次拿最小的兩個數加總
2.加總之後,丟回去排列,再拿最小的兩個數加總
3.持續上面兩個步驟即可

跟ACM 10954一樣

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

#include<stdio.h>
#include<stdlib.h>
main()
{
 int n,m;
 while(scanf("%d",&n)==1&&n!=0)
   {
    short int number[20001]={0},mm=n;
     while(n--)
       {
        scanf("%d",&m);
        number[m]++;
       }
    int line[30001]={0};
    int a,b,c,top=0;
    for(a=1;a<=20000;a++)
     if(number[a]!=0)
      for(b=0;b<number[a];b++)
       {line[top]=a;top++;}
    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("%d\n",ans);
   }
 return 0;
}