题目链接
AcWing 730. 机器人跳跃问题 - AcWing
一些话
// 这里我用了浮点二分，mid = (l + r) / 2，最后再手动写了个向上取整的句子，所以没有wa，可能是题目数据太弱。
切入点
游戏目标是到达第 N个建筑，在这个过程中能量值不能为负数个单位。
现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？
机器人在满足条件的情况下能通过的建筑数量与初始能量值正相关，符合二分特性
流程
//二分check部分是个小模拟，按照模拟步骤写伪代码，然后等价替换
// 递推，枚举每一个台阶，然后对mid操作，每次操作后判断mid是否跳出了0~1e5的区间，小于0return false，大于0return true;
// 枚举结束了后return true；
等价替换后的伪代码：
// 写check函数伪代码（流程）的时候可以发现，不管mid和f[i]的大小关系如何，最终都是mid = 2 * mid - f[i];
// 因此写代码时就不用再分情况讨论，只要写一个mid = 2 * mid - f[i] 就可以了,然后还有一个剪枝操作，
// 因为f[i]max = 1e5,所以只要mid>1e5，直接return true就可以了
输出一个整数，表示所需的最少单位的初始能量值上取整后的结果。
这个我是真无语了，一直纠结yxc代码哪里用了向上取整，其实这道题不用浮点二分的话得到的答案肯定是大于浮点二分的精确小数答案的，所以用整数二分本身就是一个向上取整了
套路
二分的取整
①向上取整 mid的表示要写成
if(merge[mid] < x) l = mid + 1对应的写法
②向下取整
if(merge[mid] > x) r = mid - 1对应的写法
merge是将mid转为mid对应的x值的函数
比如数组指针转值
题目条件与对应答案
// 11:11 ~11:14读题 // ~24 ac // 向上取整 mid的表示要写成l + r + 1 >> 1即可，向下取整 mid = l + r >> 1 // 这里我用了浮点二分，mid = (l + r) / 2，最后再手动写了个向上取整的句子，所以没有wa，可能是题目数据太弱。 // 已经申请了加强数据了 //二分check部分是个小模拟，按照模拟步骤写伪代码，然后等价替换 // 写check函数伪代码（流程）的时候可以发现，不管mid和f[i]的大小关系如何，最终都是mid = 2 * mid - f[i]; // 因此写代码时就不用再分情况讨论，只要写一个mid = 2 * mid - f[i] 就可以了,然后还有一个剪枝操作， // 因为f[i]max = 1e5,所以只要mid>1e5，直接return true就可以了 #include <iostream> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; const int N = 1e5 + 10; double f[N],n,maxn; bool check(double mid){ // 递推，枚举每一个台阶，然后对mid操作，每次操作后判断mid是否跳出了0~1e5的区间，小于0return false，大于0return true; // 枚举结束了后return true； // 可推导出mid = 2 * mid - f[i]; // for(int i = 1;i <= n;i++){ if(mid >= f[i]) mid += mid - f[i]; else mid -= (f[i] - mid); if(mid < 0) return false; } return true; } int main(){ cin >> n; for(int i = 1;i <= n;i++) { scanf("%lf",&f[i]); maxn = max(f[i],maxn); } double l = 1,r = maxn; while(r - l > 1e-3){ double mid = (l + r) / 2; if(check(mid)) r = mid; else l = mid; } if(int(l * 10) % 10) l += 1; cout << (int)l << endl; return 0; }
