2019-04-14 字节跳动之第三题 机器人跳跃问题

解析：

这个题目读完题，马上想到二分的方法去解题。

但是写完代码提交之通过了2%的用例，也就是只通过一个用例。

楼主绞尽脑汁去寻找错误，找了半天才发现原来会出现自己当前能量值超int范围甚至超long long导致判断出错。这个bug确实有点难以想到，要是不能当场知道对错，好不容易想到二分提交却只能通过一个用例恐怕要哭死。

代码如下：

#include<iostream>

#include<cstdio>

using namespace std;

int h[100005]={0};

int n;

bool ok(int m)

{

for(int i=0;i<n;++i)

{

m=2*m-h[i];

if(m<0) return false;

if(m>=100000) return true;//第一次提交缺少该语句导致错误

}

return true;

}

int main()

{

scanf("%d",&n);

for(int i=0;i<n;++i)

{

scanf("%d",&h[i]);

}

int result=100000;

int j=100000;

int i=1;

while(i<=j)

{

int m=i+(j-i)/2;

if(ok(m))

{

if(m<result) result=m;

j=m-1;

}

else

{

i=m+1;

}

}

printf("%d\n",result);

return 0;

}

这次字节跳动的笔试题只做了两题，总体来说这次笔试的难度还是挺高的，估计差不多要具有ACM区域赛铜的水平才能通过这次笔试。剩下的题目没有截图，难度跟这两题差不多吧，楼主水平有限只能做两题了。