730. 机器人跳跃问题(二分答案)

730. 机器人跳跃问题(二分答案)

本题可以用二分答案的思想来做 

二分：二段性+单调性

由于本题是在数轴上找到一个最小的元素，所以具有二段性

 同时是在数轴上寻找的，所以本题具有单调性

 

 我们可以发现，只要check()(满足条件)，就去左边寻找满足条件的第一个元素，反之则去右边寻找，所以二分查找可以满足条件

check()怎么写呢？

由于每次跳了一次后，他的能量都会变成2e-h

1.假如他在任意一点的e小于0，说明它必然是跳不到最后了，return false

2.假如他在任意一点的e大于H_max(给的数据中的最大高度)，那么说明他一定能跳到最后 return true

e=h_max ,   2e-h_max  ==  e=h_max   循环下去，必然满足

#include 
#include 
using namespace std;
const int N = 100001;
int h[N];
int n;

bool check(int x)
{
	for (int i = 0;i < n;i++)
	{
		x = 2 * x - h[i];	//先跳再计算他的能量
		if (x >= N) return true;
		if (x < 0) return false;
		
	}
	return true;
}
int main()
{
	
	cin >> n;
	for (int i = 0;i < n;i++)
		cin >> h[i];
	int l = 0, r = N;
	while (l < r)
	{
		int mid = l + r >> 1;
		if (check(mid))	//满足条件，往左走
			r = mid;
		else
			l = mid + 1;
	}
	cout << l;
}