A13002 | Antenna Coverage
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
The mayor of the Central Town wants to modernize Central Street, represented in this problem by the $(Ox)$ axis.
On this street, there are $n$ antennas, numbered from $1$ to $n$ . The $i$ -th antenna lies on the position $x_i$ and has an initial scope of $s_i$ : it covers all integer positions inside the interval $[x_i - s_i; x_i + s_i]$ .
It is possible to increment the scope of any antenna by $1$ , this operation costs $1$ coin. We can do this operation as much as we want (multiple times on the same antenna if we want).
To modernize the street, we need to make all integer positions from $1$ to $m$ inclusive covered by at least one antenna. Note that it is authorized to cover positions outside $[1; m]$ , even if it's not required.
What is the minimum amount of coins needed to achieve this modernization?
On this street, there are $n$ antennas, numbered from $1$ to $n$ . The $i$ -th antenna lies on the position $x_i$ and has an initial scope of $s_i$ : it covers all integer positions inside the interval $[x_i - s_i; x_i + s_i]$ .
It is possible to increment the scope of any antenna by $1$ , this operation costs $1$ coin. We can do this operation as much as we want (multiple times on the same antenna if we want).
To modernize the street, we need to make all integer positions from $1$ to $m$ inclusive covered by at least one antenna. Note that it is authorized to cover positions outside $[1; m]$ , even if it's not required.
What is the minimum amount of coins needed to achieve this modernization?
输入格式
The first line contains two integers $n$ and $m$ ( $1 \le n \le 80$ and $n \le m \le 100\ 000$ ).
The $i$ -th of the next $n$ lines contains two integers $x_i$ and $s_i$ ( $1 \le x_i \le m$ and $0 \le s_i \le m$ ).
On each position, there is at most one antenna (values $x_i$ are pairwise distinct).
The $i$ -th of the next $n$ lines contains two integers $x_i$ and $s_i$ ( $1 \le x_i \le m$ and $0 \le s_i \le m$ ).
On each position, there is at most one antenna (values $x_i$ are pairwise distinct).
输出格式
You have to output a single integer: the minimum amount of coins required to make all integer positions from $1$ to $m$ inclusive covered by at least one antenna.
输入输出样例
输入 #1
3 595 43 2 300 4 554 10
输出 #1
281
输入 #2
1 1 1 1
输出 #2
0
输入 #3
2 50 20 0 3 1
输出 #3
30
输入 #4
5 240 13 0 50 25 60 5 155 70 165 70
输出 #4
26
In the first example, here is a possible strategy:
- Increase the scope of the first antenna by $40$ , so that it becomes $2 + 40 = 42$ . This antenna will cover interval $[43 - 42; 43 + 42]$ which is $[1; 85]$
- Increase the scope of the second antenna by $210$ , so that it becomes $4 + 210 = 214$ . This antenna will cover interval $[300 - 214; 300 + 214]$ , which is $[86; 514]$
- Increase the scope of the third antenna by $31$ , so that it becomes $10 + 31 = 41$ . This antenna will cover interval $[554 - 41; 554 + 41]$ , which is $[513; 595]$
Total cost is $40 + 210 + 31 = 281$ . We can prove that it's the minimum cost required to make all positions from $1$ to $595$ covered by at least one antenna.
Note that positions $513$ and $514$ are in this solution covered by two different antennas, but it's not important.
—
In the second example, the first antenna already covers an interval $[0; 2]$ so we have nothing to do.
Note that the only position that we needed to cover was position $1$ ; positions $0$ and $2$ are covered, but it's not important.
- Increase the scope of the first antenna by $40$ , so that it becomes $2 + 40 = 42$ . This antenna will cover interval $[43 - 42; 43 + 42]$ which is $[1; 85]$
- Increase the scope of the second antenna by $210$ , so that it becomes $4 + 210 = 214$ . This antenna will cover interval $[300 - 214; 300 + 214]$ , which is $[86; 514]$
- Increase the scope of the third antenna by $31$ , so that it becomes $10 + 31 = 41$ . This antenna will cover interval $[554 - 41; 554 + 41]$ , which is $[513; 595]$
Total cost is $40 + 210 + 31 = 281$ . We can prove that it's the minimum cost required to make all positions from $1$ to $595$ covered by at least one antenna.
Note that positions $513$ and $514$ are in this solution covered by two different antennas, but it's not important.
—
In the second example, the first antenna already covers an interval $[0; 2]$ so we have nothing to do.
Note that the only position that we needed to cover was position $1$ ; positions $0$ and $2$ are covered, but it's not important.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted