题目描述
机器人正在玩一个古老的基于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:
样例
输入格式
第一行输入整数N。
第二行是N个空格分隔的整数,H(1),H(2),…,H(N)代表建筑物的高度。
输出格式
输出一个整数,表示所需的最少单位的初始能量值上取整后的结果。
经过分析:如果H(k+1)>E,那么机器人就失去H(k+1)-E的能量值,否则它将得到E-H(k+1)的能量值。
如果H(k+1)>E,E=E-(H(k+1)-E)=2E-H[k+1];否则E=E+E-H[k+1]=2E-H[k+1];存在单调性,可以想到用二分
所以无论任何情况E=2*E-H[k+1];如果在跳的过程中其中E>=过MaxH(MaxH是建筑的最高建筑长度),则必定整个过程中的E都大于0,
因为E=E+E-H[k+1]=E+MaxH-H[k+1]=MaxH+一个大于0的数,整体E必大于MaxH,下一步E=E+E-H[k+1];E会一直大于MaxH,E往后的过程必定大于0
所以E的范围0到MaxH,H[i]的最大范围100000,所以E的范围0到100000,所以l=0,r=100000
解法1
如果跳完最后一个建筑后的E仍然大于0,则说明整个过程中的E均大于0;所以从0个建筑开始跳,跳到最后一个的建筑E>=0的最小E0(最初的E)即可,
跳完最后一个的建筑E>=0返回true,跳的过程中E>100000返回true,
解法2
跳的过程中E>100000返回true,跳的过程中E<0就false,否则返回true
出错点:mid要是double型的,因为mid=2mid-H[i],mid=1e5时,2mid会爆int
解法1
#include <iostream>
#include <cstdio>
using namespace std;
int n,k;
int H[100005];
bool check(double mid){
for(int i=0;i<n;i++){
mid=2*mid-H[i];
if(mid>100000) return true; //这一句写不写都可以过,但是写的话时间会快一半,发现存在E>MaxH了,直接true了,因为最后必定是大于0的,上面已经解释过了
}
if(mid>=0) return true; //跳完E>=0,返回true
return false; //否则返回false
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&H[i]);
}
int l=0,r=100000; //上面有解释
while(l<r){ //模板
double mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%d\n",l);
}
解法2
#include <iostream>
#include <cstdio>
using namespace std;
int n,k;
int H[100005];
bool check(double mid){
for(int i=0;i<n;i++){
mid=2*mid-H[i];
if(mid>100000) return true; //这一句写不写都可以过,但是写的话时间会快一半,发现存在E>MaxH了,直接true了,因为最后必定是大于0的,上面已经解释过了
if(mid<0) return false;
}
return true;
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&H[i]);
}
int l=0,r=100000; //上面有解释
while(l<r){ //模板
double mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%d\n",l);
}