C++哈工科教103010打怪兽 求帮助

Question

103010.打怪兽
难度普及+/提高
内存256MB
时间3000ms
题目描述
在一款电脑游戏中，你需要打败
只怪物（从 1到 n编号）。

为了打败第 i
只怪物，你需要消耗 d(i)
点生命值，但怪物死后会掉落血药，使你恢复 a(i)
点生命值。

任何时候你的生命值都不能降到
（0或 以下）。

请问是否存在一种打怪顺序，使得你可以打完这
只怪物而不死掉。

输入格式
第一行两个整数 n,z
，分别表示怪物的数量和你的初始生命值。

接下来
n行，每行两个整数 d(i) a(i)
。

输出格式
第一行为 TAK（是）或 NIE（否），表示是否存在这样的顺序。

如果第一行为 TAK，则第二行为空格隔开的
的排列，表示合法的顺序。

输入输出测试点
输入 #1
复制
3 5
3 1
4 8
8 3
输出 #1
复制
TAK
2 3 1

Answer 1

贪心算法，我们先根据它打败这个怪兽后，是收益还是亏损，分为两个数组，我这里用了一个pair数组，pair数组里面存两个数字，分别为亏损的，和idx（因为最后要输出编号），同时用一个数组存一下每组收益的，然后将pair两个数组排序，收益的数组，按照first从小到大，亏损的，按照从大到小。

```c++
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
typedef long long ll;
typedef pair<ll,ll> pii;
pii b[N],c[N];
ll a[N];
ll cnt1=0,cnt2=0;
ll cmp(pii x,pii y)
{
    return x.first>y.first;
}
int main() {
    ll n,z;
    cin>>n>>z;
    for(int i=0; i<n; i++) {
        ll x;
        cin>>x>>a[i];
        if(a[i]>=x) {
            b[cnt1++]= {x,i};

        } else {
            c[cnt2++]= {x,i};
        }
    }
    sort(b,b+cnt1);
    sort(c,c+cnt2,cmp);
    int flag=0;
    for(int i=0; i<cnt1; i++) {
        
        ll x=b[i].first,idx=b[i].second,y=a[idx];
        if(z>=x) {
            z=z+y-x;
        } else {
            flag=1;
            break;
        }
    }
    if(flag==0) {
        for(int i=0; i<cnt2; i++) {
            ll x=c[i].first,idx=c[i].second,y=a[idx];
            if(z>=x) {
                z=z+y-x;
            } else {
                flag=1;
                break;
            }
        }
    }
    if(flag==1) {
        puts("NIE");
    } else {
        puts("TAK");
        for(int i=0; i<cnt1; i++)
            cout<<b[i].second+1<<" ";
        for(int i=0; i<cnt2; i++)
            cout<<c[i].second+1<<" ";

    }
}
/*
3 5
3 1
4 8
8 3
*/

```