讨论/《春招冲刺班 - 7 天刷题挑战》 - 机器人跳跃问题/
《春招冲刺班 - 7 天刷题挑战》 - 机器人跳跃问题
共 12 个回复
#include <iostream>

using namespace std;

const int MAXN = 1e5 + 10;
int arr[MAXN];
int n;

bool check(int mid){
    for(int i = 0; i < n; i ++){
        mid += mid - arr[i];
        if(mid > MAXN)
            return true;
        else if(mid < 0)
            return false;
    }
    return true;
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i ++)
        cin >> arr[i];

    int le = 1, ri = MAXN, mid;
    while(le < ri){
        mid = le + ri >> 1;
        if(check(mid))
            ri = mid;
        else
            le = mid + 1;
    }
    cout << ri << endl;
    return 0;
}
1

#include <iostream>
#include <vector>
using namespace std;

int main(){
int n;
cin>>n;
vector<int> nums;
for(int i=0;i<n;i++){
int p;cin>>p;
nums.push_back(p);
}
int res=0;
for(int i=n-1;i>=0;i--)
res=(res+nums[i]+1)/2;

cout<<res<<endl;
return 0;

}

e在不断累加的情况下可能会溢出变为负值。

同学,看一下我的二分法

import java.util.Scanner;
public class Solution {
static int n;
public static void main(String[]args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
int[]h=new int[n+1];
int max=0;
for (int i = 1; i <= n; i++) {
h[i]=sc.nextInt();
max=Integer.max(max, h[i]);
}
int low=0,high=max+1;
while (low+1<high) {
int mid=low+(high-low)/2;
boolean flag=isSuccess(h,mid);
if (flag) {
high=mid;
}else {
low=mid;
}
}
int res=isSuccess(h,low)?low:high;
System.out.println(res);

}
private static boolean isSuccess(int[] h, int e) {
// TODO Auto-generated method stub
for (int i = 0; i < h.length-1; i++) {
if (h[i+1]>e) {
e-=h[i+1]-e;
}else {
e+=e-h[i+1];
}
if (e<0) {
return false;
}
}
return true;
}
}

作者:匿名用户
链接:https://leetcode-cn.com/leetbook/read/bytedance-c01/oh6wbv/?discussion=4ECgo6
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

厉害,可以通过

设到达第N个建筑时E=0,然后从后往前更新即可求出最少初始能量。

若到达第N个建筑时能量为E2,到达第N-1个建筑时能量为E1。
则E2有
1、当H(N)>E1时,E2 = E1-(H(N)-E1),E2 = 2E1-H(N)
2、当H(N)<=E1时,E2 = E1+(E1-H(N)),E2 = 2
E1-H(N)
发现无论哪种情况,E2始终为2*E1-H(N)。
通过E2求E1可得E1 = ceil((E2+H(N))/2)(要求为整数,需向上取整)
由于H(i)的取值范围是正数,所以只要E2>=0,那么E1一定也>=0,且必为最小值。

import java.util.*;

public class Solution{
    public static void main(String[] args){
        Scanner scanner =  new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        for(int i=0;i<n;i++)a[i] = scanner.nextInt();
        int cur = 0;
        
        while(--n>=0){
            cur = (int)Math.ceil((cur+a[n])/2.0);
        }
        System.out.println(cur);
    }
}

有什么问题吗,编译器上用你的代码跑测试用例没什么问题。

思路比较简单,二分+模拟即可
使用C++的问题:数字越界,范围大概在 2^100000.
所以需要在energy那里将值拉回。

#include <iostream>
#include <vector>

using namespace std;

bool check(vector<int> &H, int energy)
{
    for (int i = 0; i < H.size() - 1; ++i)
    {
        if (H[i + 1] > energy)
            energy -= H[i + 1] - energy;
        else
            energy += energy - H[i + 1];

        energy = min(energy, int(1e5));  // 拉回int范围
        
        if (energy <= 0)
            return false;
    }
    return true;
}

int solve(vector<int> &H)
{
    int ans = 0, left = 1, right = 1e5, mid;

    while (left <= right)
    {
        mid = (left + right) >> 1;
        if (check(H, mid))
        {
            ans = mid;
            right = mid - 1;
        }
        else
            left = mid + 1;
    }
    
    return ans;
}

int main()
{
    int N;
    cin >> N;
    vector<int> H(N + 1, 0);
    for (int i = 1; i <= N; ++i)
        cin >> H[i];
        
    cout << solve(H) << endl;

    return 0;
}

同学,可以看一下我下面的代码吗?