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; }