[PA2014]Bohater

BZOJ

题意:在一款电脑游戏中，你需要打败\(n(n<=100000)\)只怪物（从1到n编号）.为了打败第i只怪物，你需要消耗\(a[i]\)点生命值，但怪物死后会掉落血药，使你恢复\(b[i]\)点生命值。任何时候你的生命值都不能降到0（或0以下）.请问是否存在一种打怪顺序，使得你可以打完这n只怪物而不死掉.

分析:很明显的贪心策略,首先打能够回血的怪物,再打剩下的怪物.而能够回血的怪物中,按照消耗的生命值从小到大排序(保证先打能打的).剩下的怪物按照回血量从大到小排序(反正都是掉血,保证每次回血尽量多一点)

排序后模拟做就好了.然后记得开\(long\) \(long\).

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=100005;
struct ppx{int x,y,id;}c[N],d[N];
inline bool cmp1(ppx x,ppx y){return x.x<y.x;}
inline bool cmp2(ppx x,ppx y){return x.y>y.y;}
int main(){
    int n=read();ll m=read(),tot=0,sum=0;
    for(int i=1;i<=n;++i){
        int a=read(),b=read();
        if(a<=b){
            c[++tot].x=a;
            c[tot].y=b;
            c[tot].id=i;//便于输出方案
        }//能够回血的放一起
        else{
            d[++sum].x=a;
            d[sum].y=b;
            d[sum].id=i;
        }//剩下的放一起
    }
    sort(c+1,c+tot+1,cmp1);
    sort(d+1,d+sum+1,cmp2);//分别排序
    for(int i=1;i<=tot;++i){//模拟
        m-=c[i].x;
        if(m<=0){puts("NIE");return 0;}
        m+=c[i].y;
    }
    for(int i=1;i<=sum;++i){//模拟
        m-=d[i].x;
        if(m<=0){puts("NIE");return 0;}
        m+=d[i].y;
    }
    puts("TAK");
    for(int i=1;i<=tot;++i)printf("%d ",c[i].id);
    for(int i=1;i<=sum;++i)printf("%d ",d[i].id);
    return 0;
}