[C++]입국심사[백준 3079]

입국심사대 N이 10만,   입국 처리인원이 10억으로 Max값이 주어진다. 각 심사대에서 처리하는데 소요되는 시간 또한 10억이다. 완탐으로 1초안에 해결이 불가능한 문제이다. 
이걸 완탐돌린다면... 생각만 해도 끔찍하다. 

착안해낸 아이디어
1. 하한값을 1로 잡고 상한값을 10억*10만값으로 가정하고 풀이하였다.
    (WorstCase: 각 심사대10억*10만)

2.  이분탐색으로 시간을 가정하고 해당 시간으로 10만의 심사대에서 처리하고자하는 인원 M을 처리할
     수 있는지 혹은 처리하기에 시간이 부족한지를 살펴본다. 

3. 처리시간이 부족하다면 하한을 중간값+1로 설정하여 중간값을 다시 설정하고 이분탐색을 진행한다. 
    인원처리가 가능하다면 상한값을 중간값-1로 설정하여 left값이 right를 초과하는 순간 종료된다. 

4. lft는 항상 최소한의 가능한순간까지의 하한값을 증가시킬것이다. right값을 lft값이 초과하는 순간
   빠져나와버리므로 수용가능한 경우의 최소 mid값과 lft값은 일치한다. 
시간 복잡도 :  O(NlogN) 
탐색과정을 보면 다음과 같다 

<code>

// pda_pro12
#include<iostream>
#include<algorithm>
#define N_ 100000
#define Upper 100000000000000   // N_ * M(max)
 
using namespace std;
 
typedef long long ll;
ll lft, rgt, n, m;   int a[N_];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) 
        cin >> a[i];
 
    ll lft = 1;  ll rgt = Upper;   // Lower ,  Upper
 
    while (lft <= rgt) {
        
        ll mid = (lft + rgt) >> 1;
        ll Sum = 0;
        for (int i = 0; i < n; i++)
            Sum += (mid / a[i]);
        if (Sum >= m)
            rgt = mid - 1; 
        else
            lft = mid+1;
    }
    cout << lft << '\n';
    return 0;
}