题目描述

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 

题目分析

贪心 先从伤害小到大打能加血的 再从加血大到小打掉血的

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
long long z;
struct your
{
    int a,b,num;
}q[100100];
int cmp(your j,your k)
{
    int x=j.b-j.a;
    int y=k.b-k.a;
    if(x>=0&&y>=0) return j.a<k.a;
    else if(x*y<=0) return x>=0;
    else return j.b>k.b; 
}
int main()
{
    scanf("%d%lld",&n,&z);
    for(int i=1;i<=n;i++) scanf("%d%d",&q[i].a,&q[i].b),q[i].num=i;
    sort(q+1,q+n+1,cmp);
    int flag=0;
    for(int i=1;i<=n;i++)
    {
        z=(long long)z-q[i].a;
        if(z<=0) 
        {
            flag=1;
            break;
        }
        z=(long long)z+q[i].b;
    } 
    if(!flag)
    {
        printf("TAK\n");
        for(int i=1;i<=n;i++) printf("%d ",q[i].num);
    }
    else printf("NIE");
    return 0;
}