No.477 MVP

Quiz

https://yukicoder.me/problems/no/477

Submit

https://yukicoder.me/submissions/336588

解法

• 他の人は数式で解いていたが、私は二分探索で解いた
• 二分探索
  • left = 0 (絶対にMVPが取れない)
  • right = inf (絶対にMVPが取れる)
  • center = (left + right) / 2
• centerダメージを与えた時、MVPに入れるかを返す関数を作る
• 計算量はlog(N)となり、解くことができました

Code

const ll inf = 1e18;

ll N, K;

bool can_beat(ll damage){
    ll rest_HP = N - damage;
    if(rest_HP<=0){
        return true;
    }

    ll n = rest_HP/K;
    if(n<damage){
        return true;
    }else{
        return false;
    }
}

int main(){
    // input
    cin >> N >> K;

    if(N<=K){
        p(1);
        return 0;
    }

    ll left = 0;
    ll right = inf;

    while(left+1!=right){
        ll center = (left+right)/2;    
        if(can_beat(center)){
            right = center;
        }else{
            left = center;
        }
    }
    p(right);
    
    return 0;
}