CSES 2. Factory Machines (1620)

출처: https://cses.fi/problemset/task/1620

---

문제 설명

A factory has n machines which can be used to make products. Your goal is to make a total of t products.

For each machine, you know the number of seconds it needs to make a single product. The machines can work simultaneously, and you can freely decide their schedule.

What is the shortest time needed to make tt products?

입력  

The first input line has two integers n and t: the number of machines and products.

The next line has n integers k_1,k_2,…,k_n : the time needed to make a product using each machine.

출력 

Print one integer: the minimum time needed to make t products.

입력 예

3 7
3 2 5

출력 예

8

Explanation: Machine 1 makes two products, machine 2 makes four products and machine 3 makes one product

제약조건

• 1 <= n <= 2x10^5
• 1 <= t <= 10^9 
• 1 <= k_i <= 10^9

---

문제 풀이

여러 기계를 동시에 돌려서 필요한 물건을 가장 빨리 만드는 시간을 찾는 문제이다.

가장 최악의 경우는 제일 오래 걸리는 기계가 모든 물건을 만드는 경우이고, 이것보다는 빨리 만들거라고 생각하고 이진 탐색을 한다. 특정 시간동안 만들어진 물건의 수를 확인해서 필요한 물건보다 많이 만들면 시간을 단축하고 부족하면 늘리는 방법으로 1/2 비율로 줄여나가서 필요한 물건과 같아질때 시간을 출력한다.

프로그램 내용

...
    long mtime[nMachine];

    for (int i = 0; i < nMachine; i++) cin >> mtime[i];

    sort(mtime, mtime+nMachine);

    long min_time = 0;
    long max_time = mtime[nMachine-1]*nProduct;
    long p_time = max_time;
    while(min_time <= max_time)
        long tPrd=0;
        long t_time = (min_time+max_time)/2;

        for (int idx= 0; idx < nMachine; ++idx)
            tPrd += t_time / mtime[idx];
            if ( tPrd >= nProduct)
                break;

        if ( tPrd >= nProduct)
            max_time = t_time -1;
            p_time = min(t_time, p_time);
        else if ( tPrd < nProduct)
            min_time = t_time + 1;
...

 

Sorting and Searching ( link )