洛谷P4025 [PA2014]Bohater

题目描述

在一款电脑游戏中，你需要打败 $n$ 只怪物（从 $1$ 到 $n$ 编号）。

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

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

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

输入格式

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

接下来 $n$ 行，每行两个整数 $d_i,a_i$ 。

输出格式

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

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

如果答案有很多，你可以输出其中任意一个。（本题使用 SPJ）

输入输出样例

输入 #1

输出 #1

TAK
2 3 1

说明/提示

对于 $100\%$ 的数据， $10^5$ ， $d_i,a_ile 10^5$ ^5。

思路：作为从幼儿园就开始玩游戏的我，遇到这个题心中暗喜。打怪？就这？还绿题？我不是随便切吗？既然你给我送咕值，那我就收下了。首先这很明显是一道贪心题，那么如何排序才能得到最优策略呢？首先我们按照回血量-掉血量排序，找到打他开始掉血的那个怪的编号。然后就相当于把所有的怪分成了两部分，一部分是打完他回血，另一部分是打完他掉血。很明显，当然是先打回血的才能确保是最优策略。在打回血怪的时候，可能有的怪打死他能回很多血，但是他的伤害也很高，所以我们需要先打小怪来加血，最后再去打血多的怪。我们可以这么理解，因为打回血怪一直是在回血，所以我们可以把伤害高的放到后面，这样我们就可以打完小怪恢复充足的血量再去打BOSS。感性理解一下可以证明这样打是正确的。也就是按伤害从小到大排序，然后打。好的，前半部分解决了，那么后半部分怎么办呢？我们很容易可以想到，打回血怪的时候血越打越多，那么就越有机会来杀掉最后的BOSS，所以后打BOSS。那么打掉血怪的时候，我们应该先把BOSS打掉。因为打掉血怪的时候你一直是在掉血，如果你现在不打死他，以后你血越来越少，那就更加不可能打死他了。所以这样就找到了贪心策略：先按净增加的血量排序（掉血怪是负的），打回血怪时按伤害从小到大排序，打掉血怪时按伤害从大到小排序。

但是这样是不对的

比如我给你一组数据，在你打完回血怪的时候你还剩11滴血，这个时候有三只掉血怪，对你造成的伤害和你打死他回复的血量分别是（8,1），（4,3），（3,2），这个顺序是我们按照贪心策略打怪的顺序，然后我们发现，在打完第一只BOSS之后，你打不死第二只怪，所以NIE。但是如果我们更改一下顺序，先打死两只小怪，这个时候你还剩9滴血，是可以再去击杀BOSS的，这样就可以打死所有的怪。这个时候我们回头想一想，我们之前的贪心策略为什么不对。

让我们回到一开始打回血怪时贪心的本源，如果我现在可以打死小怪，我肯定不亏，因为至少我不会掉血。打回血怪时我不用去考虑到底能回多少血，因为我只要不掉血就行。只要保证一直在增加血量，我就有机会去打死伤害更高的怪。但是打掉血怪的时候不一样，我们还要考虑他们给予我们的回血。我们可以用一种整体的思路去考虑这个问题：我们的终极目标是打死所有的怪，那么也就是说，我们打掉血怪时受到的伤害总量是一定的，那么我们只要回复尽可能多的血量，就越有机会打死所有的怪。那么这个时候我们就得到了这道题的正解：掉血怪按照回血量从大到小排序。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long int ll;
ll n,m;
struct guai{
    ll shang,xue,hao,zeng;//汉语拼音QWQ 
}a[100010];
ll cmp1(guai x,guai y){
    return x.zeng>y.zeng;
}
ll cmp2(guai x,guai y){
    return x.shang<y.shang;
}
ll cmp3(guai x,guai y){
    return x.xue>y.xue;
}//三个阶段不同的排序 
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&a[i].shang,&a[i].xue);
        a[i].zeng=a[i].xue-a[i].shang;
        a[i].hao=i;
    }
    sort(a+1,a+1+n,cmp1);//第一阶段的排序 
    int t=0;
    for(ll i=1;i<=n;i++){
        if(a[i].zeng<0){
            sort(a+1,a+i,cmp2);
            sort(a+i,a+n+1,cmp3);
            t=1;//这里有一个细节要注意一下，如果所有的怪都是回血怪，那么它里面就没有进行排序，但是实际上我们依然要按照贪心策略进行排序。所以如果里面没有排序，那么我们就到外面排一次序 
            break;
        }
    }
    if(t==0){
        sort(a+1,a+n+1,cmp2);
    }//在外面单独排序 
    for(ll i=1;i<=n;i++){
        if(m<=a[i].shang){
            printf("NIE
");
            return 0;
        }//如果血量小于等于0，那么结束循环同时输出不能 
        m-=a[i].shang;
        m+=a[i].xue;
    }
    printf("TAK
");
    for(ll i=1;i<=n;i++){
        printf("%d ",a[i].hao);//可以的话输出编号 
    }
    return 0;
}

最后，不要忘记开longlong（10^5*10^5=10^10会爆int）