首页 > ACM题库 > HDU-杭电 > HDU 3979-Monster-贪心-[解题报告]HOJ
2015
04-14

HDU 3979-Monster-贪心-[解题报告]HOJ

Monster

问题描述 :

One day, v11 encounters a group of monsters in a foreast. In order to defend the homeland, V11 picks up his weapon and fights!

All the monsters attack v11 at the same time. Every enemy has its HP, and attack value ATK. In this problem, v11 has his ATK and infinite HP. The damage (also means reduction for HP) is exactly the ATK the attacker has. For example, if v11′s ATK is 13 and the monster’s HP is 27, then after v11′s attack, the monster’s HP become 27 – 13 = 14 and vice versa.

v11 and the monsters attack each other at the same time and they could only attack one time per second. When the monster’s HP is less or equal to 0 , we think this monster was killed, and obviously it would not attack any more. For example, v11′s ATK is 10 and a monster’s HP is 5, v11 attacks and then the monster is killed! However, a monster whose HP is 15 will be killed after v11 attack for two times. v11 will never stop until all the monsters are killed ! He wants to minimum the HP reduction for the fight! Please note that if in some second, some monster will soon be killed , the monster’s attack will works too.

输入:

The first line is one integer T indicates the number of the test cases. (T <=100)

Then for each case, The first line have two integers n (0<n<=10000), m (0<m<=100), indicates the number of the monsters and v11′s ATK . The next n lines, each line has two integers hp (0<hp<=20), g(0<g<=1000) ,indicates the monster’s HP and ATK.

输出:

The first line is one integer T indicates the number of the test cases. (T <=100)

Then for each case, The first line have two integers n (0<n<=10000), m (0<m<=100), indicates the number of the monsters and v11′s ATK . The next n lines, each line has two integers hp (0<hp<=20), g(0<g<=1000) ,indicates the monster’s HP and ATK.

样例输入:

2 
3 1 
1 10 
1 20 
1 40 
1 10 
7 3

样例输出:

Case #1: 110 
Case #2: 3

听戴牛讲完这题体会了排序不等式在贪心中的作用

这个题说的是后很多怪兽同时攻击一个游侠,怪兽有不同的血量和攻击力。游侠有一个攻击力,如果选择攻击怪兽的顺序使得游侠扣血最少

贪心构造:对于2只怪兽,A,B;假设当前怪兽总攻击值为V。

设怪兽A的攻击力,和被攻击次数(攻击多少次死亡) 为 GA,CA;

设怪兽B的攻击力,和被攻击次数(攻击多少次死亡) 为 GB,CB;

可知,如果先攻击怪兽A,后攻击怪兽B ,那么游侠的去血量分别为

正在杀怪兽A :V *CA ,怪兽A死亡后,正在杀怪兽B :(V-GA) * CB ;

杀完两只怪兽的去血总量为 SUM1 = V *CA + (V-GA) * CB;

同理,先攻击怪兽B,后攻击怪兽A ,SUM2 = V *CB + (V-GB) * CA;

我们知道,去血最少,即要取min ( SUM1,SUM2 );

令SUM1 < SUM2;

则  V *CA + (V-GA) * CB < V *CB + (V-GB) * CA

化简为 GB*CA < GA*CB

以此条件排序,贪心即可。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
using namespace std;
struct point{
       int hp;
       int a;       
}mon[10005];
int m;
int cmp(const void * a,const void * b){
        struct point *aa=(struct point *)a;
        struct point *bb=(struct point *)b;
        return (int)ceil((double)aa->hp/m) * bb->a  -  aa->a * (int)ceil((double)bb->hp/m);
}
int main(){
    int t,T,i;
    int n;
    scanf("%d",&T);
    int ca=0;
    for(t=1;t<=T;t++){
                      scanf("%d %d",&n,&m);
                      for(i=1;i<=n;i++){
                                        scanf("%d %d",&mon[i].hp,&mon[i].a);                  
                      }                  
                      qsort(&mon[1],n,sizeof(mon[1]),cmp);
                      __int64  sum=0,t=0;
                      for(i=1;i<=n;i++){
                                        t+=(__int64 )ceil((double)mon[i].hp/(double)m);
                                        sum+=(__int64 )mon[i].a*t;                                                      
                      }
                      printf("Case #%d: ",++ca);
                      printf("%I64d\n",sum);
    }
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/waitfor_/article/details/7215267