3709: [PA2014]Bohater
Time Limit: 5 Sec Memory Limit: 128 MBSec Special Judge
Submit: 339 Solved: 109
[Submit][Status]
Description
在一款电脑游戏中，你需要打败n只怪物（从1到n编号）。为了打败第i只怪物，你需要消耗d[i]点生命值，但怪物死后会掉落血药，使你恢复a[i]点生命值。任何时候你的生命值都不能降到0（或0以下）。请问是否存在一种打怪顺序，使得你可以打完这n只怪物而不死掉
Input
第一行两个整数n,z(1<=n,z<=100000)，分别表示怪物的数量和你的初始生命值。
接下来n行，每行两个整数d[i],a[i](0<=d[i],a[i]<=100000)
Output
第一行为TAK（是）或NIE（否），表示是否存在这样的顺序。
如果第一行为TAK，则第二行为空格隔开的1~n的排列，表示合法的顺序。如果答案有很多，你可以输出其中任意一个。
Sample Input
3 5
3 1
4 8
8 3
3 1
4 8
8 3
Sample Output
TAK
2 3 1
2 3 1
HINT
Source
题解：
刚开始贪心贪错了，以为扣血的应该按扣血量从大往小打，不然现在不打扣了血怎么打。。。
然后发现了这个反例：
5滴血，一只扣3血回3血，一只扣4血回0……
T_T
忘记现在能打的情况了。。。
hzwer：
倒序来看，相当于将血药吐出来然后返还杀怪的消耗，那么显然也是按照损失体力（即血药回血量）升序，正回来即是降序。。。
代码：
刚开始贪心贪错了，以为扣血的应该按扣血量从大往小打，不然现在不打扣了血怎么打。。。
然后发现了这个反例：
5滴血，一只扣3血回3血，一只扣4血回0……
T_T
忘记现在能打的情况了。。。
hzwer：
倒序来看，相当于将血药吐出来然后返还杀怪的消耗，那么显然也是按照损失体力（即血药回血量）升序，正回来即是降序。。。
代码：
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 100005
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 1000000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
int n,l,r;
struct rec{int x,y,id;}b[maxn];
ll hp;
bool flag;
inline bool cmp1(rec a,rec b)
{
return a.x<b.x;
}
inline bool cmp2(rec a,rec b)
{
return a.y>b.y;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
n=read();hp=read();
l=;r=n+;
for1(i,n)
{
int x=read(),y=read();
if(x<y)b[++l].x=x,b[l].y=y,b[l].id=i;
else b[--r].x=x,b[r].y=y,b[r].id=i;
}
sort(b+,b+l+,cmp1);sort(b+r,b+n+,cmp2);
for1(i,n)
{
hp-=(ll)b[i].x;
if(hp<=){flag=;break;}
hp+=(ll)b[i].y;
}
if(flag)printf("NIE\n");
else
{
printf("TAK\n");
for1(i,n-)printf("%d ",b[i].id);
printf("%d\n",b[n].id);
}
return ;
}