此題屬于比較簡單的題目，讀完題(前提是你能讀完，因為它真的很長)就發現其實是貪心題目。
所以，直接，排序，貪心，AC.下面是代碼:
1 #include<stdio.h>
2 #include<algorithm>
3 int n,m;
4 int heads[20010];
5 int knights[20010];
6 7 8 int cmp(
const void *first,
const void * second)
9 {
10 return *((
int*)first) - *((
int*)second);
11 }
12 13 //返回-1表示不可能
14 int deal()
15 {
16 if(n > m)
17 return -1;
18 qsort(heads,n,
sizeof(
int),cmp);
19 qsort(knights,m,
sizeof(
int),cmp);
20 int i = 0,j = 0;
21 int total = 0;
22 for(i = 0;i < n;++i)
23 {
24 while(knights[j] < heads[i] && j < m)
25 {
26 ++ j;
27 }
28 if(j == m)
29 break;
30 else 31 {
32 total += knights[j];
33 ++j;
34 }
35 }
36 if(i == n)
37 return total;
38 else 39 return -1;
40 41 }
42 43 int main()
44 {
45 int i;
46 int result;
47 while(scanf("%d%d",&n,&m))
48 {
49 if(m == 0 &&n == 0)
50 break;
51 for(i = 0;i < n;++i)
52 {
53 scanf("%d",&heads[i]);
54 }
55 for(i = 0;i < m;++i)
56 {
57 scanf("%d",&knights[i]);
58 }
59 result = deal();
60 if(result == -1)
61 {
62 printf("Loowater is doomed!\n");
63 }
64 else 65 {
66 printf("%d\n",result);
67 }
68 }
69 return 0;
70 }
posted on 2012-04-06 20:43
崔佳星 閱讀(194)
評論(0) 編輯 收藏 引用 所屬分類:
xoj