A6955 | 饥饿的奶牛
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
有一条奶牛冲出了围栏，来到了一处圣地（对于奶牛来说），上面用牛语写着一段文字。
现用汉语翻译为：
有 $N$ 个区间，每个区间 $x,y$ 表示提供的 $x\sim y$ 共 $y-x+1$ 堆优质牧草。你可以选择任意区间但不能有重复的部分。
对于奶牛来说，自然是吃的越多越好，然而奶牛智商有限，现在请你帮助他。
现用汉语翻译为：
有 $N$ 个区间，每个区间 $x,y$ 表示提供的 $x\sim y$ 共 $y-x+1$ 堆优质牧草。你可以选择任意区间但不能有重复的部分。
对于奶牛来说，自然是吃的越多越好，然而奶牛智商有限，现在请你帮助他。
输入格式
第一行一个整数 $N$。
接下来 $N$ 行，每行两个数 $x,y$，描述一个区间。
接下来 $N$ 行，每行两个数 $x,y$，描述一个区间。
输出格式
输出最多能吃到的牧草堆数。
输入输出样例
输入 #1
3 1 3 7 8 3 4
输出 #1
5
数据范围
$1 \leq n \leq 1.5 \times 10^5$，$0 \leq x \leq y \leq 3 \times 10^6$。
样例分析
可选区间及收益（长度）：
1.
[1, 3]：收益 $3 - 1 + 1 = \mathbf{3}$2.
[7, 8]：收益 $8 - 7 + 1 = \mathbf{2}$3.
[3, 4]：收益 $4 - 3 + 1 = \mathbf{2}$冲突判断：
- 区间
[1, 3]和[3, 4]在位置 3 重叠，不能同时选。 - 区间
[7, 8]离得很远，跟谁都不冲突，必选（收益 +2）。 - 方案 A：选
[1, 3]+[7, 8]$\rightarrow$ 总收益 $3 + 2 = \mathbf{5}$ - 方案 B：选
[3, 4]+[7, 8]$\rightarrow$ 总收益 $2 + 2 = 4$
决策比较：
方案 A 收益最大，输出 5。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？