A7163 | 午枫打砖块
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
小午和小枫迷上了一款叫做《打砖块》的游戏。
在这个游戏中，一共有 $n$ 行砖块，每行都有 $10^9$ 个砖块，其中有 $n$ 组奖励砖，每组奖励砖从 $1$ 到 $n$ 编号，第 $i$ 组奖励砖位于第 $i$ 行，从左起第 $l_i$ 列到第 $r_i$ 列的范围。摧毁这些奖励砖才能够得到分数。
小午和小枫发射的弹球可以一次将连续的 $d$ 列内所有砖块都打碎。形式化地，每次可以选择一个 $1$ 到 $10^9-d+1$ 之间的整数 $x$ ，将第 $x$ 列到第 $x+d-1$ 列范围内的所有砖块都摧毁。由于奖励砖是连在一起的大砖块，所以奖励砖只要被摧毁某一块小砖块就会被整个摧毁。
请问小午和小枫至少需要发射多少次弹球才能摧毁所有的奖励砖？
在这个游戏中，一共有 $n$ 行砖块，每行都有 $10^9$ 个砖块，其中有 $n$ 组奖励砖，每组奖励砖从 $1$ 到 $n$ 编号，第 $i$ 组奖励砖位于第 $i$ 行，从左起第 $l_i$ 列到第 $r_i$ 列的范围。摧毁这些奖励砖才能够得到分数。
小午和小枫发射的弹球可以一次将连续的 $d$ 列内所有砖块都打碎。形式化地，每次可以选择一个 $1$ 到 $10^9-d+1$ 之间的整数 $x$ ，将第 $x$ 列到第 $x+d-1$ 列范围内的所有砖块都摧毁。由于奖励砖是连在一起的大砖块，所以奖励砖只要被摧毁某一块小砖块就会被整个摧毁。
请问小午和小枫至少需要发射多少次弹球才能摧毁所有的奖励砖？
输入格式
第一行输入两个整数 $n,d$ ，分别表示砖块的行数和发射一次能够摧毁的列数。
接下来 $n$ 行，每行输入两个整数 $l_i,r_i$ ，分别表示第 $i$ 行奖励砖的范围。
接下来 $n$ 行，每行输入两个整数 $l_i,r_i$ ，分别表示第 $i$ 行奖励砖的范围。
输出格式
输出一个整数，表示摧毁所有奖励砖需要发射的最少次数。
输入输出样例
输入 #1
3 3 1 2 4 7 5 9
输出 #1
2
输入 #2
3 3 1 2 4 7 4 9
输出 #2
1
样例解释
样例解释 1
下图展示了与输入样例 $1$ 对应的砖块分布。
例如，可以按照如下方式进行发射弹球，仅用 $2$ 次即可摧毁所有的奖励砖。
- 首先，将 $[2, 4]$ 列摧毁。位于 $[2, 4]$ 的奖励砖 $1$ 和奖励砖 $2$ 被摧毁。
- 然后将 $[5, 7]$ 列摧毁。位于 $[5, 7]$ 的墙 $3$ 受到伤害，被摧毁。
样例解释 2
与输入输出样例 $1$ 相比，奖励砖 $3$ 的范围从 $[5, 9]$ 变成了 $[4, 9]$。
在这种情况下，只需对 $[2, 4]$ 进行一次拳击即可摧毁所有的墙。
数据范围
对于 $100\%$ 的数据，满足：$1\leq n\leq 2\times 10^5,1\leq d\leq 10^9,1\leq l_i\leq r_i\leq 10^9$ 。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？