竞赛题: 合并果子 etc.(做完一道 go on)

yarco1

合并果子

【问题描述】
    在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

    每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

    因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

    例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。

【输入文件】

    输入文件fruit.in包括两行，第一行是一个整数n(1<＝n<=10000)，表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai(1<＝ai<=20000)是第i种果子的数目。

【输出文件】

    输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。

【样例输入】

3
1 2 9

【样例输出】

15

【数据规模】

对于30％的数据，保证有n<=1000：
对于50％的数据，保证有n<=5000；
对于全部的数据，保证有n<=10000。

go on~~~
本贴子不欢迎guan shui, 以及无聊者.

回复格式:
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. }
    

复制代码

yarco1

靠, 这个明天做...

虫食算

【问题描述】
    所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：

       43#9865#045
    +    8468#6633
       44445506978

    其中#号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是5和3，第二行的数字是5。

    现在，我们对问题做两个限制：

    首先，我们只考虑加法的虫食算。这里的加法是N进制加法，算式中三个数都有N位，允许有前导的0。

    其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。如果这个算式是N进制的，我们就取英文字母表午的前N个大写字母来表示这个算式中的0到N-1这N个不同的数字：但是这N个字母并不一定顺序地代表0到N-1)。输入数据保证N个字母分别至少出现一次。

            BADC
      +    CRDA
            DCCC

    上面的算式是一个4进制的算式。很显然，我们只要让ABCD分别代表0123，便可以让这个式子成立了。你的任务是，对于给定的N进制加法算式，求出N个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解，

【输入文件】
    输入文件alpha.in包含4行。第一行有一个正整数N(N<=26)，后面的3行每行有一个由大写字母组成的字符串，分别代表两个加数以及和。这3个字符串左右两端都没有空格，从高位到低位，并且恰好有N位。

【输出文件】
    输出文件alpha.out包含一行。在这一行中，应当包含唯一的那组解。解是这样表示的：输出N个数字，分别表示A，B，C……所代表的数字，相邻的两个数字用一个空格隔开，不能有多余的空格。

【样例输入】
5
ABCED
BDACE
EBBAA

【样例输出】
1 0 3 4 2

【数据规模】
对于30％的数据，保证有N<＝10；
对于50％的数据，保证有N<＝15；
对于全部的数据，保证有N<＝26。

yarco1

...数据规模...什么意思...
有更好的想法...发欧....
goon go on`

yzc2002

第一题用qsort不好，当源数据基本是排好序的时候，qsort是效率是最低的
建议用二叉树

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

yarco1

楼上的, qing教了. 您贴个代码吧...

当源数据基本是排好序的时候

这什么意思?没排好吧...什么是基本排好序了?

强烈希望楼上的贴代码

yzc2002

原帖由 yarco1 于 2005-11-7 11:02 发表
楼上的, 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);
        }

第一次循环当然是没排过序的，但以后呢？除了最后一个数，其它都是从大到小排序的
用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. }
    

复制代码

set在STL里是用红黑树表示的

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

yarco1

谢了, 明白了.

对了...那个set...
不能放相同数字的吧?

yzc2002

原帖由 yarco1 于 2005-11-8 12:56 发表
谢了, 明白了.

对了...那个set...
不能放相同数字的吧?

那就改成用multiset