【蓝桥杯题解】acwing730. 机器人跳跃问题

acwing730. 机器人跳跃问题

• 🌟题目
• 🌟思路
• 🌟C++代码
• 🌟最后

)

---

前言：
欢迎关注我的专栏专栏链接,里面是我刷过的蓝桥杯真题 ，有题目链接 + 题解。

🚀🚀🚀

🌟题目

GOGOGO

🌟思路

• 根据题意退出 能量公式 E‘ = 2 * E - H[ i + 1]
• 思路：递推每一个数能否成立，然后二分查找答案，时间复杂度O(n logn) 满足题意10⁵：O（n）/O（n logn）

🌟C++代码

#include 
using namespace std;
const int N = 100010;
int h[N];
int n;

bool check (int mid) {// mid ：E
    for(int i = 1; i <=n ; i ++) {
      mid = mid * 2 - h[i ];
      if(mid < 0) return false;
      if(mid >= 1e5) return true;
      //必须特判，如果超过1e5还一直乘下去会溢出(mid 变成负数)哪怕ll也一样
    }
    return true;
}
int main () {
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> h[i];
    }
    int l = 1, r = 1e5;
    while (l < r) {
        int mid = l + r >> 1;
        if(check(mid)) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    cout << r << endl;
    return 0;
}

🌟最后

感谢你能看到这里，希望对你有帮助，文章如有错误还请斧正~