백준 3079 입국심사 혼내주기

 

이분 탐색으로 lower bound를 찾으면 되는 문제. t초동안 몇명이 심사대를 통과할 수 있는지 구하는 과정에서 무작정 더하면 overflow가 발생한다는 것을 캐치하지 못해 삽질을 했다. M의 범위보다 커지면 탈출하게 해줘서 해결.

 

#include <iostream>
#include <vector>
using namespace std;

#define ll long long

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> v(n);
    for(int i = 0; i < n; ++i)
        cin >> v[i];
    
    ll left = 0, right = 1e18;
    while(left < right){
        ll mid = (left + right) / 2;

        ll t = 0;
        for(int i = 0; i < n; ++i){
            t += mid / v[i];
            if(t > 1e18) break;
        }
        
        if(t >= m) right = mid;
        else left = mid+1;
    }

    cout << left;
}