ABC023 D - 射撃王

D: 射撃王 - AtCoder Beginner Contest 023 | AtCoder

解説

最小値をx[m]以下にできるかどうかで二分探索。

tを風船iがx[m]を超えない時間とすると、

H_i + t * S_i = xより、

t = (x - H_i) / S_i

となる。これが風船iを割らなければいけない制限時間である。全ての風船の制限時間を求め、制限時間の小さい方から0秒から割っていく。制限時間を超えてしまう風船があったらx[m]以下にできない。

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int N;
ll H[100005], S[100005];
// x[m]以下にできるかどうか
bool calc(ll x) {
  int T[N];
  FOR(i,0,N) {
    if(x - H[i] < 0) return false;
    T[i] = min((ll)111110, (x - H[i]) / S[i]);
  }
  sort(T, T + N);
  FOR(i,0,N) if(T[i] < i) return false;
  return true;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N;
  FOR(i,0,N) cin >> H[i] >> S[i];
  ll l = 0, r = 1e16;
  while(r - l > 1) {
    ll m = (r + l) / 2;
    if(calc(m)) r = m;
    else l = m;
  }
  if(!calc(r)) r = l; 
  cout << r << endl;
  return 0;
}