BZOJ-3709-[PA2014]Bohater(贪心)
2024-10-14 17:53:34
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
题解
这道题是贪心
这里我们考虑两种情况
第一种是d[i]<a[i]的,就是打完能够回血的,显然我们需要按d[i]升序
第二种是d[i]>a[i],即打怪只会扣血,我们倒着推,假设打完这些怪兽后剩余血量为x,那么倒着推到前面的血量就是x+d[i]-a[i],这样的情况和情况一是差不多的,又因为是倒着推的,所以我们要按a[i]降序
#include<bits/stdc++.h>
#define N 100005
#define ll long long
using namespace std;
int n,x,y,cnt,num;
ll z;
struct node{
int fee,rec,id;
}a[N],b[N];
bool cmp(node x,node y){ return x.fee<y.fee; }
bool cmp1(node x,node y){ return x.rec>y.rec; }
int main(){
scanf("%d%lld",&n,&z);
for (int i=;i<=n;i++){
scanf("%d%d",&x,&y);
if (x<=y) a[++cnt].fee=x,a[cnt].rec=y,a[cnt].id=i;
else b[++num].fee=x,b[num].rec=y,b[num].id=i;
}
sort(a+,a++cnt,cmp);
for (int i=;i<=cnt;i++)
if (z>a[i].fee) z+=a[i].rec-a[i].fee;
else{ puts("NIE"); return ; }
sort(b+,b++num,cmp1);
for (int i=;i<=num;i++)
if (z>b[i].fee) z+=b[i].rec-b[i].fee;
else{ puts("NIE"); return ; }
puts("TAK");
for (int i=;i<=cnt;i++)
printf("%d ",a[i].id);
for (int i=;i<=num-;i++)
printf("%d ",b[i].id);
printf("%d\n",b[num].id);
return ;
}
最新文章
- Basic Tutorials of Redis(1) - Install And Configure Redis
- DELPHI类声明方式简介
- 02、AngularJs的数据绑定
- mysql in 命令
- 通过LINQ表达式树动态构建查询条件
- java基础(十九)IO流(二)
- android4.3环境搭建
- 本地Linux服务器上配置Git
- Zookeeper 客户端API调用示例(基本使用,增删改查znode数据,监听znode,其它案例,其它网络参考资料)
- Nmap小技巧——探测大网络空间中的存活主机
- Mysql数据库基础学习笔记
- 关于set_input_delay的用法分析
- 7.AOP编程
- @DateTimeFormat(pattern = ";yyyy-MM-dd HH:mm:ss";) 前台request 获取body的格式是正确的 (2018-03-23 16:44:22) 但是Java 后台却格式化成了yyyy-MM-dd的格式 巨坑(@InitBinder搞得贵)
- 网络抓包 Fiddler
- php中@mysql_connect与mysql_connect有什么区别
- java web 验证码-数字不变形
- MFC剪贴板通信
- Array对象常用方法
- IKVM.NET入门(2)