AcWing 730. 机器人跳跃问题-O(NlogN) 和 O(N) 的两种解法
原题链接
中等
作者:
saltedfish
,
2021-01-05 11:28:29
,
所有人可见
,
阅读 333
import java.util.*;
/* 解法1:二分法,时间复杂度 O(nlogn)
首先推导,当 H(k+1) > E(k) 时,E(k+1) = 2E(k) - H(k+1);
当 H(k+1) < E(k) 时,E(k+1) = 2E(k) - H(k+1); >= 0 恒成立
当 H(k+1) = E(k) 时,E(k+1) = 2E(k) - H(k+1) = E(k); >= 0 恒成立
因为当 H(k+1) <= E(k) 时,E(k+1) >= 0 恒成立,所以 E(0) 的上界为 max{H(1), ... , H(n)} <= 10^5(数据范围);
所以我们可以用二分的思想挨个试 0~10^5 之间的数,而且只要中间出现 >= 10^5 的数就一定可以。
*/
class Main {
static int n;
static int[] h;
// 遍历检查这个数是否可行
private static boolean check(int e) {
for (int i = 0; i < n; i ++) {
e = 2 * e - h[i];
if (e >= 100000) return true;
else if (e < 0) return false;
}
return true;
}
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
n = reader.nextInt();
h = new int[n];
for (int i = 0; i < n; i ++) h[i] = reader.nextInt();
int lo = 0, hi = 100000;
while (lo < hi) {
int mid = (lo + hi) >> 1;
if (check(mid)) hi = mid;
else lo = mid + 1;
}
System.out.println(lo);
}
}
/* 解法2:贪心法,时间复杂度 O(n)
因为我们推出 E(k+1) = 2E(k) - H(k+1), 要保证 E(k+1) >= 0 恒成立;我们发现 E(k+1) 是关于 E(k) 严格递增的,即假设
存在一个最小值 E(k) 使得 E(k+1) 恰好为0,那么 E(k) 增大 E(k+1) 必然也增大,我们可以从 E(n) 往前推,假设存在 E(n-1)
恰好使得 E(n) 为 0 ,那么 E(n-1) = (E(n) + H(n)) / 2, E(n-2) = (E(n-2) + H(n-2)) / 2, ... , E(0) = (E(1) + H(1)) / 2;
所以最后求出的 E(0) 必然为最小值,只需要向上取整即可。
*/
class Solution2 {
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
int n = reader.nextInt();
int[] h = new int[n];
for (int i = 0; i < n; i ++) h[i] = reader.nextInt();
double min = 0;
for (int i = n - 1; i >= 0; i --) {
min = (h[i] + min) / 2.0;
}
System.out.println((int)Math.ceil(min));
}
}