做什么网站赚钱最快,三水顺德网站建设,四川住房和城乡建设厅网站不能进入,wordpress 图片链接文章目录 原题链接题目描述输入格式输出格式数据范围输入样例1#xff1a;输出样例1#xff1a;输入样例2#xff1a;输出样例2#xff1a;输入样例3#xff1a;输出样例3#xff1a; 题目分析示例代码 原题链接
730. 机器人跳跃问题
题目难度#xff1a;中等
题目来… 文章目录 原题链接题目描述输入格式输出格式数据范围输入样例1输出样例1输入样例2输出样例2输入样例3输出样例3 题目分析示例代码 原题链接
730. 机器人跳跃问题
题目难度中等
题目来源笔试题
题目描述
机器人正在玩一个古老的基于 DOS 的游戏。
游戏中有 N1 座建筑——从 0 到 N 编号从左到右排列。
编号为 0 的建筑高度为 0 个单位编号为 iii 的建筑高度为 H ( i ) H(i) H(i) 个单位。
起初机器人在编号为 0 的建筑处。
每一步它跳到下一个右边建筑。
假设机器人在第 k 个建筑且它现在的能量值是 EEE下一步它将跳到第 k 1 k1 k1 个建筑。
如果 H ( k 1 ) E H(k1)E H(k1)E那么机器人就失去 H ( k 1 ) − E H(k1)-E H(k1)−E 的能量值否则它将得到 E − H ( k 1 ) E-H(k1) E−H(k1) 的能量值。
游戏目标是到达第 N 个建筑在这个过程中能量值不能为负数个单位。
现在的问题是机器人至少以多少能量值开始游戏才可以保证成功完成游戏
输入格式
第一行输入整数 N。
第二行是 N 个空格分隔的整数 H ( 1 ) , H ( 2 ) , … , H ( N ) H(1),H(2),…,H(N) H(1),H(2),…,H(N) 代表建筑物的高度。
输出格式
输出一个整数表示所需的最少单位的初始能量值上取整后的结果。
数据范围 1 ≤ N , H ( i ) ≤ 1 0 5 , 1 \le N,H(i) \le 10^5, 1≤N,H(i)≤105,
输入样例1
5
3 4 3 2 4 输出样例1
4 输入样例2
3
4 4 4 输出样例2
4 输入样例3
3
1 6 4 输出样例3
3 题目分析
这道题就是说一定条件下向前走会损失能量否则向前走会得到能量
第一种情况的结果就是 E − ( H k 1 − E ) 2 E − H k 1 E-(H_{k1}-E)2E-H_{k1} E−(Hk1−E)2E−Hk1
第二种的情况的结果是 E E − H k 1 2 E − H k 1 EE-H_{k1}2E-H_{k1} EE−Hk12E−Hk1
也就是说不管情况如何他经过一个台阶的结果都是 2 E − H k 1 2E-H_{k1} 2E−Hk1
问最少要多少能量可以走完全程
这里我们可以注意到假设存在一个最小的满足要求的值那么只要一个大于他的值就必然是满足要求的而对于小于他的值就必然是不满足要求的
这其实就是一种单调性的体现这个题就可以使用二分的思想
我们判断时调用判断的函数如果mid的值满足要求说明大于等于mid的值一定是满足要求的答案应该是在mid值或者mid的左侧说明此时我们应当将右边界缩小变为R mid否则就是L mid 1
示例代码
#includeiostream
using namespace std;const int N 100010;int n;
int h[N];bool check(int e)
{for (int i 1; i n; i) // 递推每一个位置的能量值{e e * 2 - h[i];if (e 1e5)return true; // 当e大于最大的高度也就是1e5时后面的能量一定是递增的因此直接返回true即可if (e 0)return false; // 当e小于0时后面的能量一定是递减的是负数因此直接返回false}return true;
}int main()
{cin n;for (int i 1; i n; i) cin h[i];int l 0, r 1e5;while (l r){int mid l r 1;if (check(mid)) r mid;else l mid 1;}cout l \n;return 0;
}
