發表新討論
#1983: 還不夠快嗎?

Unknown User

d221. 10954 - Add All -- UVa10954 | From: [60.244.132.1] | 發表日期 : 2009-05-17 07:01

這題我的想法是:

1. 排序數列

2.把數列最小兩個的A[0]+A[1]相加得到值B 在把B加入 Cost   

3.把在數列中的A[0]跟A[1]刪除 , 並將 B加入數列中

4.如果數列的大小等於1就結束,否則回到步驟1

5. 印出Cost值

問題是現在上傳後一直TLE , 難道是排序的地方效率有問題嗎?

我是用STL的sort來做的 , 這樣難道是要我自己寫Insert sort才能解決嗎?

#include <stdio.h>
#include <algorithm>
using namespace std;
unsigned int Number[5001],N,T,Sum,Temp,Total;
bool compare(int  A ,int  B)
{
    if ( A<B )
    {
        return 1;
    }
    return 0;
}
int main()
{
    while (scanf("%d",&N))
    {

       /*Input*/
       if (N ==0)
       {
           break;
       }
       for (T =0 ; T < N ;T++)
       {
           scanf("%d",&Number[T]);
       }
       /**/

       /*Algorithm*/
       sort(Number,Number+N,compare);
       Sum=Number[0];
       Temp=0;
       Total=0;
       while (N-1 > Temp)
       {
           Sum=(Number+Temp)[1]+(Number+Temp)[0];
           (Number+Temp)[1]=Sum;
           sort(Number+Temp,Number+N,compare);
           Total=Total+Sum;
           Temp++;
       }
       printf("%d\n",Total);
       /**/
    }
    return 0;
}


 
#1984: Re:還不夠快嗎?


morris1028 (碼畜)

學校 : 國立花蓮高級中學
編號 : 3529
來源 : [114.37.59.62]
最後登入時間 ：
2021-07-12 19:00:43
d221. 10954 - Add All -- UVa10954 | From: [118.161.216.224] | 發表日期 : 2009-05-17 07:42
在下提供一個1.2秒的方式
1.首先先將給的數字排序好
2.每作一次加總,就做一次泡泡[因為加總之後一定會大於第3小的數]
3.利用泡泡把加總的數移到定位
4.之後在拿最小的2個數字做加總
5.一直重複2~4 步驟
因為是泡泡效率並不怎麼好,用累堆排序會更快,不過我不會`XD
STL是什麼...=口=
#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;
}
 
#1985: Re:還不夠快嗎?

Unknown User

d221. 10954 - Add All -- UVa10954 | From: [60.244.132.1] | 發表日期 : 2009-05-17 10:09

我看懂m大開 int number[100001] 的用意了

聰明的辦法  這樣就不用跑排序了省了很多 swap 的時間

STL是C++提供的一個很有彈性的 資料結構 和 演算法 的類別庫

 
ZeroJudge Forum