A9707 | Minimum Difficulty
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
Mike is trying rock climbing but he is awful at it.
There are $n$ holds on the wall, $i$ -th hold is at height $a_{i}$ off the ground. Besides, let the sequence $a_{i}$ increase, that is, $a_{i}<a_{i+1}$ for all $i$ from 1 to $n-1$ ; we will call such sequence a track. Mike thinks that the track $a_{1}$ , ..., $a_{n}$ has difficulty . In other words, difficulty equals the maximum distance between two holds that are adjacent in height.
Today Mike decided to cover the track with holds hanging on heights $a_{1}$ , ..., $a_{n}$ . To make the problem harder, Mike decided to remove one hold, that is, remove one element of the sequence (for example, if we take the sequence $(1,2,3,4,5)$ and remove the third element from it, we obtain the sequence $(1,2,4,5)$ ). However, as Mike is awful at climbing, he wants the final difficulty (i.e. the maximum difference of heights between adjacent holds after removing the hold) to be as small as possible among all possible options of removing a hold. The first and last holds must stay at their positions.
Help Mike determine the minimum difficulty of the track after removing one hold.
There are $n$ holds on the wall, $i$ -th hold is at height $a_{i}$ off the ground. Besides, let the sequence $a_{i}$ increase, that is, $a_{i}<a_{i+1}$ for all $i$ from 1 to $n-1$ ; we will call such sequence a track. Mike thinks that the track $a_{1}$ , ..., $a_{n}$ has difficulty . In other words, difficulty equals the maximum distance between two holds that are adjacent in height.
Today Mike decided to cover the track with holds hanging on heights $a_{1}$ , ..., $a_{n}$ . To make the problem harder, Mike decided to remove one hold, that is, remove one element of the sequence (for example, if we take the sequence $(1,2,3,4,5)$ and remove the third element from it, we obtain the sequence $(1,2,4,5)$ ). However, as Mike is awful at climbing, he wants the final difficulty (i.e. the maximum difference of heights between adjacent holds after removing the hold) to be as small as possible among all possible options of removing a hold. The first and last holds must stay at their positions.
Help Mike determine the minimum difficulty of the track after removing one hold.
输入格式
Mike is trying rock climbing but he is awful at it.
There are $n$ holds on the wall, $i$ -th hold is at height $a_{i}$ off the ground. Besides, let the sequence $a_{i}$ increase, that is, $a_{i}<a_{i+1}$ for all $i$ from 1 to $n-1$ ; we will call such sequence a track. Mike thinks that the track $a_{1}$ , ..., $a_{n}$ has difficulty . In other words, difficulty equals the maximum distance between two holds that are adjacent in height.
Today Mike decided to cover the track with holds hanging on heights $a_{1}$ , ..., $a_{n}$ . To make the problem harder, Mike decided to remove one hold, that is, remove one element of the sequence (for example, if we take the sequence $(1,2,3,4,5)$ and remove the third element from it, we obtain the sequence $(1,2,4,5)$ ). However, as Mike is awful at climbing, he wants the final difficulty (i.e. the maximum difference of heights between adjacent holds after removing the hold) to be as small as possible among all possible options of removing a hold. The first and last holds must stay at their positions.
Help Mike determine the minimum difficulty of the track after removing one hold.
There are $n$ holds on the wall, $i$ -th hold is at height $a_{i}$ off the ground. Besides, let the sequence $a_{i}$ increase, that is, $a_{i}<a_{i+1}$ for all $i$ from 1 to $n-1$ ; we will call such sequence a track. Mike thinks that the track $a_{1}$ , ..., $a_{n}$ has difficulty . In other words, difficulty equals the maximum distance between two holds that are adjacent in height.
Today Mike decided to cover the track with holds hanging on heights $a_{1}$ , ..., $a_{n}$ . To make the problem harder, Mike decided to remove one hold, that is, remove one element of the sequence (for example, if we take the sequence $(1,2,3,4,5)$ and remove the third element from it, we obtain the sequence $(1,2,4,5)$ ). However, as Mike is awful at climbing, he wants the final difficulty (i.e. the maximum difference of heights between adjacent holds after removing the hold) to be as small as possible among all possible options of removing a hold. The first and last holds must stay at their positions.
Help Mike determine the minimum difficulty of the track after removing one hold.
输出格式
Print a single number — the minimum difficulty of the track after removing a single hold.
输入输出样例
输入 #1
3 1 4 6
输出 #1
5
输入 #2
5 1 2 3 4 5
输出 #2
2
输入 #3
5 1 2 3 7 8
输出 #3
4
In the first sample you can remove only the second hold, then the sequence looks like $(1,6)$ , the maximum difference of the neighboring elements equals 5.
In the second test after removing every hold the difficulty equals 2.
In the third test you can obtain sequences $(1,3,7,8)$ , $(1,2,7,8)$ , $(1,2,3,8)$ , for which the difficulty is 4, 5 and 5, respectively. Thus, after removing the second element we obtain the optimal answer — 4.
In the second test after removing every hold the difficulty equals 2.
In the third test you can obtain sequences $(1,3,7,8)$ , $(1,2,7,8)$ , $(1,2,3,8)$ , for which the difficulty is 4, 5 and 5, respectively. Thus, after removing the second element we obtain the optimal answer — 4.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted