ABC023 D問題 射撃王

風船が上がっていくのを撃ち落としてなるべく撃ち落す風船の最大の高さが最小になるようにする問題

最近こういう問題多く見る気がする。
最大、最小を求める系の問題である程度値が大きくて時間足りないよぉ><みたいなときは２分探索を疑ったほうが良い。
ある高さ以内で撃ち落とせるかを判定して、それを二分探索すれば簡単に求まる。
make_pairのところを間違ってP(defineでpairにしてる)を使ってしまってcastされて死んでて全然気付かなかったのがとても残念。

const int MAX_N = 100001;
ll N;
ll H[MAX_N], S[MAX_N];

bool OK(ll x){
    pair<ll, ll> St[N];
    for(ll i=0; i<N; i++){
        St[i] = make_pair((x-H[i])/S[i], i);
    }
    sort(St, St+N);
    for(ll i=0; i<N; i++){
        ll index = St[i].second;
        if(H[index]+S[index]*i > x) return false;
    }
    return true;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N;
    for(int i=0; i<N; i++){
        cin >> H[i] >> S[i];
    }

    ll low = 0, high = 1e15;
    while(high-low > 1){
        ll mid = (low+high)/2;
        if(OK(mid)) high = mid;
        else low = mid;
    }
    cout << high << endl;
}