hdu4415 不错的想法题

题意:

一个人他有一定的血,有一些怪物,他去杀怪物,有的怪物杀死他后还可以在不费自己血的情况下任意杀死一些怪物,问你他最多杀死多少怪物,在最多杀怪前提下最好用多少血,(大体题意是这样).

思路:

首先我们把怪物分成两个集合,A一个是杀死他后可以免费杀死其他人的,B另一个是杀死他后不能免费杀死其他人的,分析下我们会发现,A集合我们只要杀死其中一个人就可以免费杀死其他人(肯定杀费血最少的),而且很有可能会攒下一些杀死B集合的机会.

其实无非两种情况,杀A集合的和不杀A集合的,如果杀选择杀A集合的那么我们肯定全杀掉,而花费的血就是A集合中血最少的那个,然后我们再把出了刚刚杀的那个以外,和B集合的所有放在一起排序称为C,杀完A集合后会剩下一下免费杀人的机会,我们用这些机会去杀C中的人,既然是免费的肯定从最大的开始杀,杀完后如果没杀没的话我们就用自己的血从小的开始在接着杀,一直杀到自己血没活着敌人没了未知,这是第一种情况,第二种情况是不杀A集合的,只杀B集合的,这种好办,直接把B排序一便,从小的开始能杀多少杀多少,最后在两种方案中选择一个最优的输出来就行了...

/*

1 只杀bi为0的 ,排序下,直接杀就行了;

2 杀bi不为0的 ,先杀死最小的那个bi不为0的,然后得到 s = b1 + b2 + b3 +++

然后在杀死其余的 n1 + n2 - 1 - s 的怪,就ok了;

*/

#include<stdio.h>

#include<algorithm>

#define N 100000 + 100

using namespace std;

typedef struct

{

int xp ,hp;

}NODE;

NODE node1[N] ,node2[N];

bool camp(NODE a ,NODE b)

{

return a.hp < b.hp;

}

int main ()

{

int t ,i ,n ,v ,n1 ,n2;

int ans1_n ,ans2_n ,ans1_hp ,ans2_hp;

int cas = 1 ,s;

scanf("%d" ,&t);

while(t--)

{

scanf("%d %d" ,&n ,&v);

n1 = n2 = s = 0;

NODE temp;

for(i = 1 ;i <= n ;i ++)

{

scanf("%d %d" ,&temp.hp ,&temp.xp);

if(temp.xp)

{

node2[++n2] = temp;

s += temp.xp;

}

else

node1[++n1] = temp;

}

ans1_n = ans1_hp = 0;

sort(node1 + 1 ,node1 + n1 + 1 ,camp);

int vv = v;

for(i = 1 ;i <= n1 ;i ++)

{

if(vv < node1[i].hp) break;

ans1_n ++;

ans1_hp += node1[i].hp;

vv -= node1[i].hp;

}

sort(node2 + 1 ,node2 + n2 + 1 ,camp);

if(v < node2[1].hp)

{

printf("Case %d: %d %d\n" ,cas ++ ,ans1_n ,ans1_hp);

continue;

}

ans2_n = 1;

ans2_hp = node2[1].hp;

v -= node2[1].hp;

if(s >= n1 + n2 - 1)

{

ans2_n = n1 + n2;

if(ans1_n > ans2_n || ans1_n == ans2_n && ans1_hp < ans2_hp)

printf("Case %d: %d %d\n" ,cas ++ ,ans1_n ,ans1_hp);

else

printf("Case %d: %d %d\n" ,cas ++ ,ans2_n ,ans2_hp);

continue;

}

for(i = 2 ;i <= n2 ;i ++)

node1[++n1] = node2[i];

sort(node1 + 1 ,node1 + n1 + 1 ,camp);

n1 -= s;

vv = v;

ans2_n += s;

for(i = 1 ;i <= n1 ;i ++)

{

if(vv < node1[i].hp) break;

vv -= node1[i].hp;

ans2_n ++;

ans2_hp += node1[i].hp;

}

if(ans1_n > ans2_n || ans1_n == ans2_n && ans1_hp < ans2_hp)

printf("Case %d: %d %d\n" ,cas ++ ,ans1_n ,ans1_hp);

else

printf("Case %d: %d %d\n" ,cas ++ ,ans2_n ,ans2_hp);

}

return 0;

}

巴特西

hdu4415 不错的想法题

最新文章

热门文章