此题属于比较简单的题目,读完题(前提是你能读完,因为它真的很长)就发现其实是贪心题目。
所以,直接,排序,贪心,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
崔佳星 阅读(179)
评论(0) 编辑 收藏 引用 所属分类:
xoj