競賽題: 合并果子 etc.(做完一道 go on)

yarco1

合并果子

【問題描述】
    在一個果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。

    每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和。可以看出，所有的果子經(jīng)過n-1次合并之后，就只剩下一堆了。多多在合并果子時總共消耗的體力等于每次合并所耗體力之和。

    因為還要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節(jié)省體力。假定每個果子重量都為1，并且已知果子的種類數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計出合并的次序方案，使多多耗費的體力最少，并輸出這個最小的體力耗費值。

    例如有3種果子，數(shù)目依次為1，2，9�？梢韵葘�1、2堆合并，新堆數(shù)目為3，耗費體力為3。接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為12，耗費體力為12。所以多多總共耗費體力=3+12=15�？梢宰C明15為最小的體力耗費值。

【輸入文件】

    輸入文件fruit.in包括兩行，第一行是一個整數(shù)n(1<＝n<=10000)，表示果子的種類數(shù)。第二行包含n個整數(shù)，用空格分隔，第i個整數(shù)ai(1<＝ai<=20000)是第i種果子的數(shù)目。

【輸出文件】

    輸出文件fruit.out包括一行，這一行只包含一個整數(shù)，也就是最小的體力耗費值。輸入數(shù)據(jù)保證這個值小于231。

【樣例輸入】

3
1 2 9

【樣例輸出】

15

【數(shù)據(jù)規(guī)�！�

對于30％的數(shù)據(jù)，保證有n<=1000：
對于50％的數(shù)據(jù)，保證有n<=5000；
對于全部的數(shù)據(jù)，保證有n<=10000。

go on~~~
本貼子不歡迎guan shui, 以及無聊者.

回復(fù)格式:
1. 程序
2. 可能的說明
3. 其它

[ 本帖最后由 yarco1 于 2005-11-7 00:54 編輯 ]

angelanpan

Huffman編碼？

yarco1

1. 
   
2. #include <stdio.h>
   
3. #include <string.h>
   
4. #include <stdlib.h>
   
5. 
   
6. #define MAX_BUF 1024
   
7. 
   
8. void get_total(int*);
   
9. int* get_numbers(const int);
   
10. int cmp(const void*, const void*);
    
11. 
    
12. int main()
    
13. {
    
14.         int n, i;
    
15.         int *vector, *total;
    
16.         int all = 0;
    
17.        
    
18.         //get total & numbers
    
19.         get_total(&n);
    
20.         vector = get_numbers(n);
    
21.         n--;
    
22.         total = (int*) malloc(sizeof(int)*n);
    
23.         for(i=0; i<n; i++) {
    
24.                 qsort(vector, n-i+1, sizeof(int), cmp);
    
25.                 *(vector+n-i-1) += *(vector+n-i);
    
26.                 *(total+i) = *(vector+n-i-1);
    
27.         }
    
28.        
    
29.         //get total
    
30.         for(i=0; i<n; i++)
    
31.                 all += *(total+i);
    
32.         printf("Total cost is: %dn", all);
    
33.        
    
34.         free(total);
    
35.         free(vector);
    
36.         return 0;
    
37. }
    
38. 
    
39. void get_total(int* n)
    
40. {
    
41.         printf("Get input: ");
    
42.         scanf("%d", n);
    
43.         getchar();  //jump over 'n'
    
44. }
    
45. 
    
46. int* get_numbers(const int total) //fuck, 還是這里處理輸入麻煩
    
47. {
    
48.         char buf[MAX_BUF], *tmp;
    
49.         int i = 1;
    
50.         int* p;
    
51.        
    
52.         memset(buf, 0, MAX_BUF);
    
53.         printf("Get each number of fruit:n");
    
54.         fgets(buf, MAX_BUF-1, stdin);
    
55.         p = (int*) malloc(total*sizeof(int));
    
56.         tmp = strtok(buf, " ");
    
57.         *p = atoi(tmp);
    
58.         //printf("%dn", *p);exit(0);
    
59.         while (i<total) {
    
60.                 tmp = strtok(NULL, " ");
    
61.                 *(p+i) = atoi(tmp);
    
62.                 i++;
    
63.         }
    
64.         return p;
    
65. }
    
66. 
    
67. int cmp(const void* left, const void* right)
    
68. {
    
69.         const int* l = (const int*) left;
    
70.         const int* r = (const int*) right;
    
71.         return *l < *r;
    
72. }
    

復(fù)制代碼

yarco1

靠, 這個明天做...

蟲食算

【問題描述】
    所謂蟲食算，就是原先的算式中有一部分被蟲子啃掉了，需要我們根據(jù)剩下的數(shù)字來判定被啃掉的字母。來看一個簡單的例子：

       43#9865#045
    +    8468#6633
       44445506978

    其中#號代表被蟲子啃掉的數(shù)字。根據(jù)算式，我們很容易判斷：第一行的兩個數(shù)字分別是5和3，第二行的數(shù)字是5。

    現(xiàn)在，我們對問題做兩個限制：

    首先，我們只考慮加法的蟲食算。這里的加法是N進制加法，算式中三個數(shù)都有N位，允許有前導(dǎo)的0。

    其次，蟲子把所有的數(shù)都啃光了，我們只知道哪些數(shù)字是相同的，我們將相同的數(shù)字用相同的字母表示，不同的數(shù)字用不同的字母表示。如果這個算式是N進制的，我們就取英文字母表午的前N個大寫字母來表示這個算式中的0到N-1這N個不同的數(shù)字：但是這N個字母并不一定順序地代表0到N-1)。輸入數(shù)據(jù)保證N個字母分別至少出現(xiàn)一次。

            BADC
      +    CRDA
            DCCC

    上面的算式是一個4進制的算式。很顯然，我們只要讓ABCD分別代表0123，便可以讓這個式子成立了。你的任務(wù)是，對于給定的N進制加法算式，求出N個不同的字母分別代表的數(shù)字，使得該加法算式成立。輸入數(shù)據(jù)保證有且僅有一組解，

【輸入文件】
    輸入文件alpha.in包含4行。第一行有一個正整數(shù)N(N<=26)，后面的3行每行有一個由大寫字母組成的字符串，分別代表兩個加數(shù)以及和。這3個字符串左右兩端都沒有空格，從高位到低位，并且恰好有N位。

【輸出文件】
    輸出文件alpha.out包含一行。在這一行中，應(yīng)當包含唯一的那組解。解是這樣表示的：輸出N個數(shù)字，分別表示A，B，C……所代表的數(shù)字，相鄰的兩個數(shù)字用一個空格隔開，不能有多余的空格。

【樣例輸入】
5
ABCED
BDACE
EBBAA

【樣例輸出】
1 0 3 4 2

【數(shù)據(jù)規(guī)�！�
對于30％的數(shù)據(jù)，保證有N<＝10；
對于50％的數(shù)據(jù)，保證有N<＝15；
對于全部的數(shù)據(jù)，保證有N<＝26。

yarco1

...數(shù)據(jù)規(guī)模...什么意思...
有更好的想法...發(fā)歐....
goon go on`

yzc2002

第一題用qsort不好，當源數(shù)據(jù)基本是排好序的時候，qsort是效率是最低的
建議用二叉樹

[ 本帖最后由 yzc2002 于 2005-11-7 09:15 編輯 ]

yarco1

樓上的, qing教了. 您貼個代碼吧...

當源數(shù)據(jù)基本是排好序的時候

這什么意思?沒排好吧...什么是基本排好序了?

強烈希望樓上的貼代碼

yzc2002

原帖由 yarco1 于 2005-11-7 11:02 發(fā)表
樓上的, qing教了. 您貼個代碼吧...

這什么意思?沒排好吧...什么是基本排好序了?

強烈希望樓上的貼代碼

        for(i=0; i<n; i++) {
                qsort(vector, n-i+1, sizeof(int), cmp);
                *(vector+n-i-1) += *(vector+n-i);
                *(total+i) = *(vector+n-i-1);
        }

第一次循環(huán)當然是沒排過序的，但以后呢？除了最后一個數(shù)，其它都是從大到小排序的
用C++來表達，不費吹灰之力

1. 
   
2. #include <iostream>
   
3. #include <set>
   
4. using namespace std;
   
5. 
   
6. int main()
   
7. {
   
8.     multiset<int> val;
   
9.     int num, x, y;
   
10.     long long total;
    
11. 
    
12.     cin >> num;
    
13.     for(int i=0; i< num; i++)
    
14.     {
    
15.         cin >> x;
    
16.         val.insert(x);
    
17.     }
    
18. 
    
19.     total = 0;
    
20.     multiset<int>::iterator itr;
    
21.     while(val.size() > 1)
    
22.     {
    
23.         itr = val.begin();
    
24.         x = *itr;
    
25.         val.erase(itr);
    
26.         itr = val.begin();
    
27.         y = *itr;
    
28.         val.erase(itr);
    
29.         total += x + y;
    
30.         val.insert(x+y);
    
31.     }
    
32.     cout << total << endl;
    
33. }
    

復(fù)制代碼

set在STL里是用紅黑樹表示的

[ 本帖最后由 yzc2002 于 2005-11-8 13:30 編輯 ]

yarco1

謝了, 明白了.

對了...那個set...
不能放相同數(shù)字的吧?

yzc2002

原帖由 yarco1 于 2005-11-8 12:56 發(fā)表
謝了, 明白了.

對了...那個set...
不能放相同數(shù)字的吧?

那就改成用multiset