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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(1)

随笔分类

随笔档案

文章分类

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜