UVa 11292 Dragon of Loowater

　　很直接的一道题，排序比较就行了，不过还是超时了一次，因为一不小心写成死循环了。。。

　　代码如下:

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 const int maxn = 20000+10;
 6 int h[maxn], k[maxn];
 7 
 8 int main()
 9 {
10 #ifdef LOCAL
11     freopen("in", "r", stdin);
12 #endif
13     int n, m;
14     while(scanf("%d%d", &n, &m) != EOF && n && m)
15     {    
16         for(int i = 0; i < n; i++)
17             scanf("%d", &h[i]);
18         for(int i = 0; i < m; i++)
19             scanf("%d", &k[i]);
20         sort(h, h+n);
21         sort(k, k+m);
22         int i, j = 0;
23         int flag = 1;
24         int sum = 0;
25         for(i = 0; i < n; i++)
26         {
27             while(1)
28             {
29                 if(j >= m)
30                 {
31                     flag = 0;
32                     break;
33                 }
34                 if(k[j] >= h[i])
35                 {
36                     sum += k[j];
37                     j++;
38                     break;
39                 }
40                 j++;
41             }
42             if(!flag)   break;
43         }
44         if(!flag)   printf("Loowater is doomed!\n");
45         else printf("%d\n", sum);
46     }
47     return 0;
48 }

Code 1

　　这是开始写的代码，把头作外层循环，让每一个骑士去找头，不仅不合正常思维，而且代码长、难理解，后来看了下书，修改代码如下：

 1 #include <cstdio>
 2 #include <algorithm>
 3 #define MAXN 20000+10
 4 using namespace std;
 5 
 6 int main()
 7 {
 8 #ifdef LOCAL
 9     freopen("in", "r", stdin);
10 #endif
11     int h[MAXN], k[MAXN];    //h[] are dragon's heads and k[] are knights
12     int n, m;    // n is the number of heads, m is the number of knights
13     while (scanf("%d%d", &n, &m) != EOF)
14     {
15         if (n == 0 && m == 0) break;
16         for (int i = 0; i < n; i++)   scanf("%d", &h[i]);
17         for (int i = 0; i < m; i++)   scanf("%d", &k[i]);
18         sort(h, h+n);
19         sort(k, k+m);
20         int cur = 0, cost = 0;
21         for (int i = 0; i < m; i++)        // for each knight
22             if (k[i] >= h[cur])
23             {
24                 cost += k[i];
25                 if (++cur >= n)   break;
26             }
27         if (cur < n)   printf("Loowater is doomed!\n");
28         else printf("%d\n", cost);
29     }
30     return 0;
31 }

Code 2

　　这下感觉不错，自然，代码也短了。然后就像看看c能比c++快多少，就又改了一下，变成c版本：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #define MAXN 20000+10
 4 
 5 int cmp(const void *_a, const void *_b)
 6 {
 7     int *a = (int*)_a;
 8     int *b = (int*)_b;
 9     return *a - *b;
10 }
11 
12 int main()
13 {
14 #ifdef LOCAL
15     freopen("in", "r", stdin);
16 #endif
17     int h[MAXN], k[MAXN];    /* h[] are dragon's heads and k[] are knights */
18     int n, m, i;    /* n is the number of heads, m is the number of knights */
19     int cur, cost;
20     while (scanf("%d%d", &n, &m) != EOF)
21     {
22         if (n == 0 && m == 0) break;
23         for (i = 0; i < n; i++)   scanf("%d", &h[i]);
24         for (i = 0; i < m; i++)   scanf("%d", &k[i]);
25         qsort(h, n, sizeof(int), cmp);
26         qsort(k, m, sizeof(int), cmp);
27         cur = 0;
28         cost = 0;
29         for (i = 0; i < m; i++)        /* for each knight */
30             if (k[i] >= h[cur])
31             {
32                 cost += k[i];
33                 if (++cur >= n)   break;
34             }
35         if (cur < n)   printf("Loowater is doomed!\n");
36         else printf("%d\n", cost);
37     }
38     return 0;
39 }

Code 3

　　结果...c++的代码用了29ms，c的代码用了32ms，有点惊讶...不过还是喜欢c++的随处声明变量的方式，强大的STL函数库、还有习惯了的注释（//注释风格在gcc的ansi选项会出错），同时还不习惯c++式的输入输出，暂时还是用c的吧，等我发现c++输入输出的好处再改啦(*^__^*) 嘻嘻……