로봇 점프 문제 (2 점)

제목 설명
로봇 은 오래된 도스 기반 게임 을 하고 있다.게임 에는 N + 1 개의 건물 이 있 습 니 다. 0 에서 N 까지 번호 가 있 고 왼쪽 에서 오른쪽으로 배열 되 어 있 습 니 다.번호 0 의 건축 높이 는 0 개 단위 이 고 번호 i 의 건축 높이 는 H (i) 개 단위 이다.처음에는 로봇 이 0 번 건물 에 있 었 다.한 걸음 한 걸음, 그것 은 다음 건물 로 뛰 어 내 렸 다.로봇 이 k 번 째 건물 에 있 고 현재 의 에너지 수 치 는 E 라 고 가정 하면 다음 단 계 는 k + 1 번 건물 로 넘 어 갈 것 이다.H (k + 1) > E 가 되면 로봇 은 H (k + 1) - E 의 에너지 수 치 를 잃 게 되 고 그렇지 않 으 면 E - H (k + 1) 의 에너지 수 치 를 얻 게 된다.게임 목 표 는 N 번 째 건물 에 도달 하 는 것 으로, 이 과정 에서 에너지 값 은 마이너스 단위 가 될 수 없다.문 제 는 로봇 이 얼마나 많은 에너지 로 게임 을 시작 해 야 게임 의 성공 을 보장 할 수 있 느 냐 하 는 것 이다.
형식 첫 줄 에 정수 N 을 입력 하 십시오.두 번 째 줄 은 N 개의 빈 칸 으로 구 분 된 정수 로 H (1), H (2), H (N) 는 건축물 의 높이 를 대표 한다.
출력 형식 은 필요 한 최소 단위 의 초기 에너지 값 을 나타 내 는 정 수 를 출력 합 니 다.
데이터 범위 1 ≤ N, H (i) ≤ 105,
입력 샘플 1: 5, 3, 4, 3, 24 출력 샘플 1: 4 입력 샘플 2: 3, 4, 4 출력 샘플 2: 4 입력 샘플 3: 3, 1, 6, 4 출력 샘플 3: 3
사고의 방향
처음으로 2 분 유형의 문 제 를 풀 었 는데 생각 이 전혀 없고 만족 하 는 성격 을 찾 지 못 했다.먼저 정수 2 분 의 절 차 를 공유 하 겠 습 니 다.
정수 2 분 의 절차: 1. 구간 [L, R] 을 찾 아 답 을 반드시 이 구간 에서 2. 판단 조건 을 찾 아 이 p 의 판단 조건 이 2 단 성 을 가지 게 하고 답 은 반드시 이 2 단 성의 분계 점 이다. 종점 M 이 이 판단 조건 에서 성립 되 는 지 분석 하고 만약 에 성립 되면 답 이 어느 구간 에 있 는 지 고려한다.성립 되 지 않 으 면 답 이 어느 구간 인지 고려 해 보 자.4. 업데이트 방식 이 R = mid 라 고 쓰 여 있 으 면 처리 하지 않 아 도 됩 니 다.업데이트 방식 이 L = mid 라면 mid 를 계산 할 때 1 을 추가 해 야 합 니 다.
그럼 이 문 제 를 살 펴 보고 먼저 구간 을 찾 아 보 자.분명히 답 은 [0, 1e 5] 이 구간 에 있다.제목 에 따 르 면 h [k + 1] > e 가 있 으 면 에너지 가 2e - h [k + 1] 손실 되 고 h [k + 1] e - h [k + 1] 가 있 으 면 제목 이 묘사 한 두 가지 상황 이 하나 가 된다.게임 을 성공 적 으로 완성 하려 면 에너지 값 이 게임 과정 에서 마이너스 가 되 지 못 하 는 성질 을 찾 았 다.우리 가 찾 아야 할 것 은 바로 이 성질 을 만족 시 키 는 최소 치 이다.다시 한 번 생각해 보면 주어진 에너지 구간 에 가장 큰 값 이 존재 할 것 이다. 만약 에 어느 순간 에 에너지 값 이 이 가장 큰 에너지 보다 크다 면 그 후의 과정 에서 에너지 값 은 마이너스 가 될 수 없 을 것 이다.다음은 답 이 어느 구간 에 있 는 지, check 프로그램 을 만족 시 켰 다 면 R 을 mid 로 업데이트 해 야 합 니 다.
AC 코드

#include
using namespace std;
const int N=1e5+10;
int h[N];
int n;
//         
bool check(int mid){
    for(int i=0;i<n;i++){
        mid=mid*2-h[i];
        if(mid>=1e5) return true;//       1e5
        if(mid<0) return false;
    }
    return true;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>h[i];
    int l=0,r=1e5;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)) r=mid;//    
        else l=mid+1;
    }
    cout<<l<<endl;
    return 0;
}