BZOJ 3709: [PA2014]Bohater

3709: [PA2014]Bohater

Time Limit: 5 Sec Memory Limit: 128 MBSec Special Judge
Submit: 1050 Solved: 352
[Submit][Status][Discuss]

Description

在一款电脑游戏中，你需要打败n只怪物（从1到n编号）。为了打败第i只怪物，你需要消耗d[i]点生命值，但怪物死后会掉落血药，使你恢复a[i]点生命值。任何时候你的生命值都不能降到0（或0以下）。请问是否存在一种打怪顺序，使得你可以打完这n只怪物而不死掉

Input

第一行两个整数n,z(1<=n,z<=100000)，分别表示怪物的数量和你的初始生命值。
接下来n行，每行两个整数d[i],a[i](0<=d[i],a[i]<=100000)

Output

第一行为TAK（是）或NIE（否），表示是否存在这样的顺序。
如果第一行为TAK，则第二行为空格隔开的1~n的排列，表示合法的顺序。如果答案有很多，你可以输出其中任意一个。

Sample Input

3 5
3 1
4 8
8 3

Sample Output

TAK
2 3 1

HINT

Source

鸣谢Jcvb

[Submit][Status][Discuss]

贪心，对于怪兽可以分成两类——

一类，打完之后血量不降反升，这些怪兽按照消耗血量从小到大排序；

一类，打完之后血量不升反降，这些怪兽按照恢复血量从大到小排序。

且血量上升怪一定排在血量下降怪前面。

易知这种打怪顺序是最优的，检测是否可行即可。

 #include <bits/stdc++.h>

 typedef long long longint;

 struct Monster {

     int a, b, id;

     Monster(void) {}

     Monster(int _a, int _b, int _id) {

         a = _a, b = _b, id = _id;

     }

 }

 mon1[],

 mon2[];

 bool cmp1(const Monster &a, const Monster &b) {

     return a.a < b.a;

 }

 bool cmp2(const Monster &a, const Monster &b) {

     return a.b > b.b;

 }

 int n;

 longint h;

 int tot1, tot2;

 signed main(void) {

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

     for (int i = , a, b; i <= n; ++i) {

         scanf("%d%d", &a, &b);

         if (a < b)

             mon1[tot1++] = Monster(a, b, i);

         else

             mon2[tot2++] = Monster(a, b, i);

     }

     std::sort(mon1, mon1 + tot1, cmp1);

     std::sort(mon2, mon2 + tot2, cmp2);

     for (int i = ; i < tot1; ++i) {

         if (h <= mon1[i].a)

             return puts("NIE"), ;

         h -= mon1[i].a;

         h += mon1[i].b;

     }

     for (int i = ; i < tot2; ++i) {

         if (h <= mon2[i].a)

             return puts("NIE"), ;

         h -= mon2[i].a;

         h += mon2[i].b;

     }

     puts("TAK");

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

         printf("%d ", mon1[i].id);

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

         printf("%d ", mon2[i].id);

     return puts(""), ;

 }

@Auhtor: YouSiki

秒客网