【PA2014】Bohater 题解（贪心）

前言：一道经典贪心题。

--------------------------

题目链接

题目大意：你有$z$滴血，要打$n$只怪。打第$i$只怪扣$d_i$滴血，回$a_i$滴血。问是否存在一种能够通关的打怪顺序。

-------------------------------

显然所有怪分为两种：扣血的怪$d_i>a_i$和回血的怪$d_i\leq a_i$。那么贪心策略是什么？

对于回血的怪，我们有若干贪心策略，例如：

1.按照$d_i$升序排列。

2.按照$a_i$降序排列。

3.按照$a_i-d_i$降序排列

$\cdots$

我们选择第一种。打个形象的比喻：假如你砍它一秒一刀$999999999$，但是它一秒一刀砍你$99999999$，你有$9999999$滴血，那显然会挂。所以我们只能从零开始打怪生活。

对于扣血的怪，我们是按照$a_i$降序排列。理由很简单：反正怎么都是扣血，我们还不如先把回血多的怪打了。反正如果你通不了关，那无论什么顺序都没有用。

在输入的时候讲怪进行分类，分别处理即可。

代码：

#include<bits/stdc++.h>

using namespace std;

int n,z;

struct node

{

    int id,d,a;

}add[],kou[];

int addcnt,koucnt;

inline int read()

{

    int x=,f=;char ch=getchar();

    while(!isdigit(ch)) {if (ch=='-')f=-;ch=getchar();}

    while(isdigit(ch)){x=x* +ch-'';ch=getchar();}

    return x*f;

}

bool cmp1(node a,node b)

{

    return a.d<b.d;

}

bool cmp2(node a,node b)

{

    return a.a>b.a;

}

int main()

{

    n=read(),z=read();

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

    {

        int b=read(),c=read();

        if (c>=b){add[++addcnt]=(node){i,b,c};}

        else{kou[++koucnt]=(node){i,b,c};}

    }

    sort(add+,add+addcnt+,cmp1);

    sort(kou+,kou+koucnt+,cmp2);

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

    {

        if (add[i].d>=z) {cout<<"NIE";return ;}

        else z=z-add[i].d+add[i].a;

    }

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

    {

        if (kou[i].d>=z) {cout<<"NIE";return ;}

        else z=z-kou[i].d+kou[i].a;

    }

    cout<<"TAK"<<endl;

    for (int i=;i<=addcnt;i++) cout<<add[i].id<<" ";

    for (int i=;i<=koucnt;i++) cout<<kou[i].id<<" ";

    return ;

}

巴特西

【PA2014】Bohater 题解（贪心）

最新文章

热门文章