BAEKJOON 3079 - AERODROM

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

문제

The Croatian delegation, consisting of M people, is travelling to IOI 2013 in Australia. They are currently waiting in a queue for check-in at the airport. There are N check-in desks open. Some officials work more efficiently than others, so the desks operate at different speeds. At the k-th desk, Tk seconds are required to finish check-in of a single passenger, and members of our delegation happen to know the exact numbers.

In the beginning, all desks are ready to accept the next passenger, and the delegation members are the only people in the queue. A person can only occupy (start check-in at) an available desk when all people in front of that person in the queue have left the queue (started, not necessarily finished, check-in) already. At that moment, the person can immediately occupy an available desk (if there is one), but can also choose to wait for another (faster) desk to become available. Our delegation members, being computer science geeks, make this decision in such a way that the moment when all of them have finished check-in is as soon as possible. Your task is finding that moment in time.

Let us describe the scenario from the first example below. There are two desks, with processing times of 7 and 10 seconds, respectively. Out of the six people in the delegation, the first two immediately occupy the two desks. At time 7, the first desk is freed, and the third person occupies it. At time 10, the fourth person occupies the second desk. At time 14, the fifth person occupies the first desk. At time 20, the second desk is freed again, but the sixth person decides to wait another second (time 21) for the first desk to become available, and then occupy it. This way, the check-in is completed by time 28. If the sixth person hadn't waited for the faster desk, the check-in would have taken a total of 30 seconds.

입력

The first line of input contains two positive integers, N (1 ≤ N ≤ 100 000), the number of desks, and M (1 ≤ M ≤ 1 000 000 000), the number of people in the delegation.

Each of the following N lines contains a number Tk from the problem statement (1 ≤ Tk ≤ 109).

출력

The first and only line of output must contain the required minimum time in seconds.

 

예제 입력 

2 6
7
10

예제 출력 

28

힌트

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #3 4번

이진 탐색으로 풀기 위해 특정 시간에 심사를 모두 처리할 수 있는지 확인하는 bool 반환 함수를 만들고, 심사를 처리할 수 있는 경우 middle 값을 올려가며 답을 찾는 방식으로 풀어봤습니다. 역시 오버 플로를 조심해야 되는 문제입니다.

#pragma warning (disable:4996)
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
 
#include <vector>
using namespace std;
typedef long long ll;
 
bool canHandle(const vector<int>& numbers, ll time, int people)
{
    ll count = 0;
    for (auto& elem : numbers)
        count += time / elem;
    return count >= people;
}
 
ll binarySearch(const vector<int>& numbers, ll low, ll high, int people)
{
    ll ret = high;
    while (low <= high)
    {
        ll mid = (low + high) / 2;
        if (!canHandle(numbers, mid, people))
        {
            low = mid + 1;
        }
        else
        {
            ret = min(ret, mid);
            high = mid - 1;
        }
    }
    return ret;
}
 
int main()
{
    int n, people, lowest, highest;
    lowest = INT_MAX;
    highest = 0;
    scanf("%d %d", &n, &people);
    vector<int> numbers(n, 0);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &numbers[i]);
        lowest = min(lowest, numbers[i]);
        highest = max(highest, numbers[i]);
    }
 
    printf("%lld\n", binarySearch(numbers, (ll)lowest * people / n, (ll)highest * people / n, people));
    return 0;
}