[백준] 3079 - 입국심사

https://www.acmicpc.net/problem/3079

3079번: 입국심사

 

파라매트릭 서치로 해결할 수 있다.

그런데 고려해야 할 점이 있다.

 

문제의 입력 제한에 N과 M을 보면, 단순히 이분 탐색의 시작과 끝을 각각 0, long long limit으로 설정할 수 있다.

하지만 다음과 같은 입력을 고려해보자.

N = 100000

M = 1000000000

모든 T_i = 1

 

그렇다면 mid가 대략 10^17이라고 할 때, mid / T_i가 N(100000)번 더해져서

10^17 * 10^5 = 10^22 => long long overflow가 발생하게 된다.

그렇다면 end를 어떻게 설정해주어야 할까?

 

그리디 하게 접근해보면, 항상 제일 많은 사람을 심사하는 입국 심사대는, T_i가 가장 작은 입국 심사대이다.

그래서 적어도 min(T_i) * m 보다는 입국 심사가 적게 걸린다.

따라서 end = min(T_i) * m으로 설정해 주었다.

 

#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;
long long a[100000], n, m;

bool query(long long mid)
{
    long long res = 0;
    for (int i = 0; i < n; i++)
    {
        res += mid / a[i];
    }
    return m <= res;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    long long start = 0, end = *min_element(a, a + n) * m;
    long long mid = (start + end) / 2, ans = LLONG_MAX;
    while (start <= end)
    {
        mid = (start + end) / 2;

        bool res = query(mid);

        if (res)
        {
            ans = min(ans, mid);
            end = mid - 1;
        }
        else
        {
            start = mid + 1;
        }
    }

    cout << ans;
}