解题：PA 2014 Bohater

我们把怪分成两类，打完了了能回血的和打完了不能回血的，然后分开打。

对于能回血的，我们先打攻击力低的，因为如果先打一个攻击力高的显然不一定能直接打过，所以先打一些攻击力低的回回血。

对于不能回血的，我们先打回血多的，因为如果能打完我们最后的血量是确定的，所以逆序来看相当于每次丢掉打怪回的血再加上打怪耗的血，这就和前面一样了。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=;

 struct a

 {

     int id;

     long long atk,hpp;

 }mon1[N],mon2[N];

 long long hp,t1,t2;

 int n,c1,c2,outp[N];

 bool cmp1(a x,a y)

 {

     return x.atk==y.atk?x.hpp>y.hpp:x.atk<y.atk;

 }

 bool cmp2(a x,a y)

 {

     return x.hpp==y.hpp?x.atk<y.atk:x.hpp>y.hpp;

 }

 int main ()

 {

     scanf("%d%lld",&n,&hp);

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

     {

         scanf("%lld%lld",&t1,&t2);

         if(t1<t2) mon1[++c1].atk=t1,mon1[c1].hpp=t2,mon1[c1].id=i;

         else mon2[++c2].atk=t1,mon2[c2].hpp=t2,mon2[c2].id=i;

     }

     sort(mon1+,mon1++c1,cmp1),sort(mon2+,mon2++c2,cmp2);

     for(int i=;i<=c1;i++)

     {

         if(hp<=mon1[i].atk) printf("NIE"),exit();

         hp+=mon1[i].hpp-mon1[i].atk,outp[++outp[]]=mon1[i].id;

     }

     for(int i=;i<=c2;i++)

     {

         if(hp<=mon2[i].atk) printf("NIE"),exit();

         hp+=mon2[i].hpp-mon2[i].atk,outp[++outp[]]=mon2[i].id;

     }

     printf("TAK\n");

     for(int i=;i<=n;i++) printf("%d ",outp[i]);

     return ;

 }

巴特西

解题：PA 2014 Bohater

最新文章

热门文章