数论_机器人跳跃(n个数的最大公约数)

机器人跳跃

题目

机器人正在玩一个古老的基于DOS的游戏。

游戏中有N+1座建筑——从0到N编号,从左到右排列。

编号为0的建筑高度为0个单位,编号为 i 的建筑高度为H(i)个单位。

起初,机器人在编号为0的建筑处。

每一步,它跳到下一个(右边)建筑。

假设机器人在第k个建筑,且它现在的能量值是E,下一步它将跳到第k+1个建筑。

如果H(k+1)>E,那么机器人就失去H(k+1)-E的能量值,否则它将得到E-H(k+1)的能量值。

游戏目标是到达第N个建筑,在这个过程中能量值不能为负数个单位。

现在的问题是机器人至少以多少能量值开始游戏,才可以保证成功完成游戏?

输入格式

第一行输入整数N。

第二行是N个空格分隔的整数,H(1),H(2),…,H(N)代表建筑物的高度。

输出格式

输出一个整数,表示所需的最少单位的初始能量值上取整后的结果。

数据范围

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

思路

? 如果H(k+1)>E,那么机器人就失去H(k+1)-E的能量值,否则它将得到E-H(k+1)的能量值。所以当前能量为E时,需要大于H(k+1)-E,并且当经过下一个建筑,能量变成 2 * E-H(k+1)。所以起始能量越高(大于答案以上),则剩余的越多。小于答案时,就会有一个建筑因为没有能量而无法跨越。不过这里有一个陷阱,每次都是 2 * E-E(k+1),所以当n较大时,就可能越界。同时当E大于最大高度的时候,之后的任何建筑都无法再能阻拦他,故判断时需要加一个特判,如果当前的能量大于最高建筑时,返回初始能量满足跨越的条件。

#include<cstdio>
#include <iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#define Max 100001
using namespace std; 
int n, a[Max], sum, l, r, mid;
bool test(int x) {
	for (int i = 1; i <= n; i++) {
		x = 2 * x - a[i];
		if (x <= 0) return false;
		if (x >= 100000) return true;
	}
	return true;
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		sum += a[i];
	} 
	r = sum;
	while (l < r) { 
		mid = (l + r) /2;
		if (!test(mid)) {
			l = mid + 1;
		}
		else {
			r = mid;
		}
	}
	cout << l << endl;
}

相关推荐