【BZOJ 3709: [PA2014]Bohater】

 

 首先，这是我n久之前培训的时候老师讲的题目了，今天突然看到，那就讲讲吧。

首先，我们考虑怎么打怪。。。

显然，我们需要保证这个怪要尽可能的打死（就是尽量不被干死），并且保证尽可能的净获得血量大的在前面

但是我们注意到，题目十分友好的说出了我们只需用输出一种方案就行

所以考虑最边界的情况（即贪心）

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

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

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

血量上升怪一定排在血量下降怪前面，易知这种打怪顺序是最优的。

最后就只需要检验每一步是否满足《活着》就可以了QwQ

千万要注意：z开long long！！

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int a=0,b=1;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            b=-1;
        c=getchar();
    }
    while(isdigit(c))
    {
        a=(a<<3)+(a<<1)+(c^48);
        c=getchar();
    }
    return a*b;
}
struct demons
{
    int id,good,bad;
}very_good[100005],very_bad[100005];
int n,good_num,bad_num;
long long z;
bool cmp1(demons a,demons b)
{
    return a.good>b.good;
}
bool cmp2(demons a,demons b)
{
    return a.bad<b.bad;
}
int main()
{
    n=read(),z=read();
    for(int i=1;i<=n;i++)
    {
        int a=read(),b=read();
        if(b>=a)
            very_good[++good_num].id=i,very_good[good_num].bad=a,very_good[good_num].good=b;
        else
            very_bad[++bad_num].id=i,very_bad[bad_num].bad=a,very_bad[bad_num].good=b;    
    }
    sort(very_good+1,very_good+good_num+1,cmp2);
    sort(very_bad+1,very_bad+bad_num+1,cmp1);
    for(int i=1;i<=good_num;i++)
    {
        if(very_good[i].bad>=z)
        {
            printf("NIE
");
            return 0;
        }
        else
            z=z-very_good[i].bad+very_good[i].good;
    }
    for(int i=1;i<=bad_num;i++)
    {
        if(very_bad[i].bad>=z)
        {
            printf("NIE
");
            return 0;
        }
        else
            z=z-very_bad[i].bad+very_bad[i].good;
    }
    printf("TAK
");
    for(int i=1;i<=good_num;i++)
        printf("%d ",very_good[i].id);
    for(int i=1;i<=bad_num;i++)
        printf("%d ",very_bad[i].id);
    return 0;
}