Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 6209 --4. 打怪闯关(monster)
6209: 4. 打怪闯关(monster)
警告!
题目
状态
题解(7)
题目描述
小O正在玩一款打怪闯关的游戏。这款游戏一共有n关,小O需要按照顺序通过这些关卡。初始小O有h点血量。如果想通过第i关,需要先与第i关的boss战斗。这次战斗会让小O降低a_i点血量,如果战斗后小O的血量小于等于0,那么他就会闯关失败。如果小O成功通过了第i关,那么它还会回复b_i的血量。 小O为了通过这款游戏,准备了很多金币。使用一枚金币可以直接秒杀某一关的怪兽,并且之后还可以获得该关卡的血量回复。小O想知道如果自己想通过,那么需要最少花费多少枚金币?
输入
第一行两个整数 n,h; 接下来 n 行,每行两个整数a_i,b_i。
输出
一行一个整数,表示答案。
样例输入输出
输入#1
复制
3 5 4 1 5 3 3 2
输出#1
复制
1
输入#2
复制
2 100 1 1 1 1
输出#2
复制
0
提示
【样例解释】 对于样例1,小O会先挑战第一关的boss,血量降到1,然后回复1点血量,血量恢复到2。然后花费1金币秒杀第二关的boss,回复3血量,血量回复到4。然后挑战第三关的boss,血量降到1,然后回复2点血量,血量恢复到3。此时共花费一枚金币,挑战成功。 【数据范围约定】 对于10%的数据,n≤2 对于30%的数据,n≤10 对于另外30%的数据,b_i=0; 对于90%的数据,n≤1000; 对于所有数据,1≤n≤〖10〗^5,1≤h≤〖10〗^4 ,0≤a_i,b_i≤〖10〗^4
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
未评定
标签
点击显示
if ($pr_flag) { ?>
递交数
203
已通过
52
} ;?>
通过率
26%
时间限制
1 秒
内存限制
256 MB
来源
2023绍兴小学
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和