AcWing 机器人跳跃问题 二分

AcWing 机器人跳跃问题 二分

 AcWing 机器人跳跃问题 二分

 AcWing 机器人跳跃问题 二分

解题思路:

如果下一个建筑的高度大于当前能量值的话:
  即如果H(k + 1) > E的话,机器人就会失去H(k + 1) - E的能量。

  那么机器人剩下的能量为E - (H(k + 1) - E) = 2 * E - H(k + 1)。

如果下一个建筑的高度小于等于当前能量值的话:

  即如果H(k + 1) <= E的话,机器人就会得到E - H(k + 1)的能量。

  那么机器人剩下的能量为E + E - H(k+ 1) = 2 * E - H(k + 1)。

所以就是说,机器人只要向右跳一下,能量均变为2 * E - H(k + 1)。

模拟下第一个样例,初始能量值为4的情况:

建筑编号:0  1  2  3  4  5

建筑高度:0  3  4  3  2  4

能量值:    4  5  6  9  16 28

所以初始能量值为4时,能保证全过程能力值不为负数。

当初始能量值为3时:

建筑编号:0  1  2  3  4  5

建筑高度:0  3  4  3  2  4

能量值:    3  3  2  1  0    -4

会出现负数,不合题意。

一般题目要求答案最少是多少,最多是多少,可以考虑用二分。

本题具有这样的性质:如果初始值为E0时可以满足题意,那么对于所有的E‘0 >= E0,也一定满足题意。

所以这个E0就是最小的满足题意的初始能力值,E0就是分界点。

然后就是细节问题了,每一次的能量值都是上一个能量值的二倍再减去一个数,如果每次都是用上一个能量值乘以二来计算当前能量值的话,有可能会超过所定义变量类型的最大数据范围。

然后又有这样一个性质:

假设所有建筑物中的最大高度为max的话,若在变化过程中,能量值E >= max的话,则之后每一步的E都 >= 0。

证明:

若这一步的E >= max,则下一步的能量值为 2 * E - h[i] = E + E - h[i] >= E + max - h[i]。

又有max - h[i] >= 0,所以下一步的能量值2 * E - h[i] >= E >= 0

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 100010;
 4 int n;
 5 int h[N];
 6 bool check(int e) { //判断能否使得初始能量为mid时,全过程能量非负 
 7     for (int i = 1; i <= n; i++) { //递推一遍即可 
 8         e = e * 2 - h[i];
 9         if (e >= 1e5) {
10             return true;
11         }
12         if (e < 0) {
13             return false;
14         }
15     }
16     return true;
17 }
18 int main() {
19     ios::sync_with_stdio(false);
20     cin.tie(0);
21     cin >> n;
22     for (int i = 1; i <= n; i++) {
23         cin >> h[i];
24     }
25     int l = -1, r = 1e5 + 10;
26     while (l < r) {
27         int mid = l + r >> 1;
28         if (check(mid)) { //如果mid满足要求的话 
29             r = mid;
30         } else {
31             l = mid + 1;
32         }
33     }
34     cout << l << endl;
35     return 0;
36 }

 

AcWing 机器人跳跃问题 二分

上一篇:基于winAMS、CasePlayer2嵌入式软件单元测试


下一篇:第一个WPF程序(串口调试)