[Greedy] 런치박스

문제 출처

https://algospot.com/judge/problem/read/LUNCHBOX

문제 내용

문제

After suffering from the deficit in summer camp, Ainu7 decided to supply lunch boxes instead of eating outside for Algospot.com winter camp.

He contacted the famous packed lunch company "Doosot" to prepare N lunch boxes for N participants. Due to the massive amount of order, Doosot was not able to prepare the same menu. Instead, they provided different N lunch boxes. Ainu7 put all the lunch boxes to a refrigerator.

The lunch time has come, and suddenly Ainu7 noticed that there is only one microwave available. As all lunch boxes are not the same, they need a different amount of time to microwave and eat. Specifically, i-th lunch box needs Mi seconds to microwave and Ei seconds to eat.

Ainu7 needs to schedule microwave usage order to minimize lunch time. Lunch time is defined as the duration from the beginning of microwaving of any lunch box to the end of eating for all participants. Write a computer program that finds minimum lunch time to help Ainu7. Note that substituting lunch while microwave is turned on is totally unnecessary, because the lunch will be cooled down.

입력

The first line of the input contains one integer T, the number of test cases.

Each test case consists of three lines. The first line of each test case contains N(1≤N≤10000), the number of the participants.

N integers will follow on the second line. They represent M1, M2, ⋯, MN.
Similarly, N integers will follow on the third line, representing E1, E2, ⋯, EN.

출력

For each test case, print the minimized lunch time in one line. It is guaranteed that the answer is always strictly less than 231.

접근

스케쥴링 문제는 그리디로 풀기에 적합하다. 먼저 그리디로 시도해보았다. 브루트포스는 2^N이 나와서 부적합하다.

풀이

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T; cin >> T;
    for (int t = 0; t < T; ++t) {
        int heatTime=0, max=-1, finishtime;
        int size; cin >> size;
        vector<pair<int, int>> arr(size);
        
        // M = microwaves
        for (int i = 0; i < size; ++ i)
            cin >> arr[i].second;
        
        // E = eat
        for (int i = 0; i < size; ++ i)
            cin >> arr[i].first;
        
        sort(arr.begin(), arr.end());
        
        for (int i = size-1; i >= 0; --i) {
            heatTime += arr[i].second;
            finishtime = heatTime + arr[i].first;
            
            max = max < finishtime ? finishtime : max;
        }
        
        cout << max << "\n";
    }
}