[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

3 5
3 1
4 8
8 3

样例输出 #1

TAK
2 3 1

提示

对于 \(100\%\) 的数据，\(1\le n,z\le 10^5\)，\(0\le d_i,a_i\le 10^5\)。

原理同luogu6927

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n;
long long m;
struct node
{
	int a,b,bj,no;
	void work()
	{
		if(a>b)bj=1;
		else if(a<b)bj=-1;
		else bj=0;
	}
};
node sz[maxn];
bool cmp(node x,node y)
{
	if(x.bj!=y.bj)return x.bj<y.bj;
	else
	{
		if(x.bj<0)return x.a<y.a||(x.a==y.a&&x.b>y.b);
		else if(x.bj==0)return x.b<y.b;
		else return x.b>y.b||(x.b==y.b&&x.a<y.a);
	}
}
int main()
{
	scanf("%d%lld",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d",&sz[i].a,&sz[i].b);
		sz[i].no=i;
		sz[i].work();
	}
	sort(sz+1,sz+1+n,cmp);
	for(int i=1;i<=n;++i)
	{
		if(m<=sz[i].a)
		{
			puts("NIE");
			return 0;
		}
		else m=m-sz[i].a+sz[i].b;
	}
	puts("TAK");
	for(int i=1;i<=n;++i) printf("%d ",sz[i].no);
	return 0;
}