题意:
一个人他有一定的血,有一些怪物,他去杀怪物,有的怪物杀死他后还可以在不费自己血的情况下任意杀死一些怪物,问你他最多杀死多少怪物,在最多杀怪前提下最好用多少血,(大体题意是这样).
思路:
首先我们把怪物分成两个集合,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
" ,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
" ,cas ++ ,ans1_n ,ans1_hp);
else
printf("Case %d: %d %d
" ,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
" ,cas ++ ,ans1_n ,ans1_hp);
else
printf("Case %d: %d %d
" ,cas ++ ,ans2_n ,ans2_hp);
}
return 0;
}