随笔-65  评论-6  文章-0  trackbacks-0
 1 /*
 2 Author:    Leo.W
 3 Descriptipn:    杀怪,以最少的失血杀掉所有的怪    。
 4 How to Do:    贪心算法,思想很好。对于杀怪顺序的权衡有这样的解释:
 5               A怪 杀伤ta,花费ca次杀此怪;B怪 杀伤tb,花费cb次;
 6               则若 (ta+tb)*ca+tb*cb<(ta+tb)*cb+ta*ca 即 需满足tb*ca<ta*tb 此时就先杀A怪
 7   */
 8 #include <stdio.h>
 9 #include <string.h>
10 #include <algorithm>
11 using namespace std;
12 #define MAXSIZES 10002
13 struct monster{
14     int hp;
15     int atk;
16     int counts;
17 };
18 monster mo[MAXSIZES];
19 int cmp(monster a,monster b){
20     return a.atk*b.counts>b.atk*a.counts;
21 }
22 int main(){
23     //freopen("in.txt","r",stdin);
24     int t,no=0;
25     scanf("%d",&t);
26     while(t--){
27         int i,mons,atk,sum=0;
28         __int64 all=0;
29         scanf("%d%d",&mons,&atk);
30         for(i=0;i<mons;i++){
31             scanf("%d%d",&mo[i].hp,&mo[i].atk);
32             if(mo[i].hp%atk==0)    mo[i].counts=mo[i].hp/atk;
33             else    mo[i].counts=mo[i].hp/atk+1;
34         }
35         sort(mo,mo+mons,cmp);
36         for(i=0;i<mons;i++){
37             sum+=mo[i].counts;
38             all+=sum*mo[i].atk;
39         }
40         printf("Case #%d: %I64d\n",++no,all);
41     }
42     return 0; 
43 } 
posted on 2012-03-08 19:05 Leo.W 阅读(115) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理