출처: 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 )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 2. Sum of Three Values (1641)  (0) 2019.10.02
CSES 2. Reading Books (1632)  (0) 2019.10.02
CSES 2. Room Allocation (1164)  (0) 2019.10.01
CSES 2. Traffic Lights (1163)  (0) 2019.10.01
CSES 2. Tasks and Deadlines (1630)  (0) 2019.09.28

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

문제 설명

There is a large hotel, and n customers will arrive soon. Each customer wants to have a single room.

You know each customer's arrival and departure day. Two customers can stay in the same room if the departure day of the first customer is earlier than the arrival day of the second customer.

What is the minimum number of rooms that are needed to accommodate all customers? And how can the rooms be allocated?

입력 양식

The first input line contains an integer n: the number of customers.

Then there are n lines, each of which describes one customer. Each line has two integers a and b: the arrival and departure day.

출력

Print first an integer kk: the minimum number of rooms required.

After that, print a line that contains the room number of each customer in the same order as in the input. The rooms are numbered 1,2,…,k 

입력 예

3
1 2
2 4
4 4

출력 예

2
1 2 1

제약조건

  • 1 <= n <= 2x10^5
  • 1 <= a <= b <= 10^9

문제 풀이 내용

도착일, 출발일과 몇번째 손님인지 저장해서, 도착일 순으로 정렬한다.

출발일과 몇개의 방이 사용중인지 priority queue 에 저장하고, 가장 빠른 출발일과 새로운 도착일을 비교해서 사용중인 방의 수를 변경한다.

프로그램 내용

더보기 
...
    vector <tuple<int, int, int>> in_schedule;

    for (int idx = 0; idx < nCus; idx++)
        in_schedule.push_back(make_tuple(arr, dep, idx));

    priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > room_q;
    vector <int> nRoom(nCus);

    sort(in_schedule.begin(), in_schedule.end());

    for (auto it = in_schedule.begin(); it != in_schedule.end(); it++)
        int arr, dep, cust_id, current;
        tie(arr, dep, cust_id) = *it;

        if (room_q.empty() || get<0>(room_q.top()) >= arr)
            current = ++room_count;                 /// used room number increase
        else
            current = get<1>(room_q.top());         /// used room number remove
            room_q.pop();

        room_q.push(make_pair(dep, current));      /// depature day, customer
        nRoom[cust_id] = current;                  /// current used room
...

 

Sorting and Searching ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 2. Reading Books (1632)  (0) 2019.10.02
CSES 2. Factory Machines (1620)  (0) 2019.10.01
CSES 2. Traffic Lights (1163)  (0) 2019.10.01
CSES 2. Tasks and Deadlines (1630)  (0) 2019.09.28
CSES 2. Towers (1073)  (0) 2019.09.28

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

문제 설명

There is a street of length x whose positions are numbered 0,1,…,x. Initially, there are no traffic lights, but n sets of traffic lights are added to the street one after another.

Your task is to calculate the length of the longest passage without traffic lights after each addition.

입력 양식

The first input line contains two integers x and n: the length of the street and the number of sets of traffic lights.

Then, the next line contains n integers p_1,p_2,…,p_n : the position of each set of traffic lights. Each position is distinct.

입력 예

8 3
3 6 2

출력 양식

Print the length of the longest passage without traffic lights after each addition.

출력 예

5 3 3

제약조건

  • 1 ≤ x ≤ 10^9
  • 1 ≤ n ≤2x10^^5
  • 0 < p_i < x

문제 풀이 내용

입력받은 가로등 위치를 set에 입력하고, 원래 있던 가로등 위치에서 가장 가까운 가로등 위치를 찾아서 간격을 계산한다. 

프로그램 내용

더보기 
...
    while(nLight--)
    {
        long temp;
        cin >> temp;

        auto it = street.lower_bound(make_tuple(temp,0));
        int pre, cur;
        tie(pre, cur) = *it;

        street.erase(it);
        street.insert(make_tuple(temp, cur-(pre-temp)));
        street.insert(make_tuple(pre, pre-temp));

        t_street.erase(make_tuple(cur,pre));
        t_street.insert(make_tuple(cur-(pre-temp), temp));
        t_street.insert(make_tuple(pre-temp, pre));

        cout << get<0>(*t_street.rbegin());
        if ( nLight > 0 ) cout << " " ;
    }
...

 

Sorting and Searching ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 2. Factory Machines (1620)  (0) 2019.10.01
CSES 2. Room Allocation (1164)  (0) 2019.10.01
CSES 2. Tasks and Deadlines (1630)  (0) 2019.09.28
CSES 2. Towers (1073)  (0) 2019.09.28
CSES 2. Playlist (1141)  (0) 2019.09.28

+ Recent posts

티스토리툴바