时隔一年我又来acwing刷题了
火眼金睛的本吗喽第一眼就看出这道机器人跳跃问题要使用 二分来计算初始能量值
然后马上写出了以下代码:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 100010;
int h[N], n, maxh;
bool check(int x)
{
int flag = true;
for(int i = 1; i <= n; i ++)
{
x = 2 * x - h[i];
cout << x << endl;
if(x < 0)
{
flag = false;
break;
}
}
return flag;
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++)
{
cin >> h[i];
maxh = max(h[i], maxh);
}
int l = 0, r = maxh;
while(l < r)
{
int mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << l << endl;
return 0;
}
在这段代码中,我使用了y总在算法基础课中讲的第一个二分模板
因为我们是要计算能够到达最后一个建筑的最小能量值
所以,我们一定要往数组的左方进行二分
而对于r,l的初始值我是这样想的:
r=0应该都能理解吧
maxh是所有建筑中的最大高度,按照题意,只要我们的能量值比某处的建筑值要高的话,那么我们就能获得能量值和建筑值之差,这个差值肯定是一个正数
那如果我们的初始值就是建筑值中的最大值呢?
这样的话,我们能够大于等于所有的建筑值,而我们的每一次比较,都会得到一个大于等于零的数字
这种情况下,我们的能量值就不可能变为0,所以可以将maxh当作二分的右边界
然后check函数我就直接很朴素的模拟了遍历数组的过程(
小声逼逼一下我记二分模板的方法:
往左方二分,即求最小值,mid不需要加一,l = mid + 1
往右方二分,即求最大值,mid需要加一,r = mid - 1
就可以简单记为左加右减
是不是一下子就记住了!哈哈哈
~然后我自信满满的点了提交~
卡在了这组数据:
30
29 2 24 14 9 17 29 22 11 13 15 30 27 19 15 30 7 24 6 4 17 18 12 24 25 11 23 27 30 27
打印了一下发现是check函数爆int了。。。真是刁钻
后面老老实实看了y总的视频课,发现check函数可以不用模拟过程
就用我上面的选择初始右边界的思路
当能量值大于等于maxh时就可以直接返回true了
bool check(int x)
{
int flag = true;
// cout << " x = " << x << endl;
for(int i = 1; i <= n; i ++)
{
x = 2 * x - h[i];
// cout << x << endl;
if(x >= maxh) return flag;//加一行这个代码就ok
if(x < 0)
{
flag = false;
break;
}
}
// cout << "flag = " << flag << endl;
return flag;
}
然后终于成功ac了
真是差一点点就能自己ac了啊,再接再厉吧