Microwaving Lunch Boxes(LUNCHBOX) 정답 코드

난이도 ★☆☆☆☆

문제를 보시려면 여기를 클릭

힌트

오래 먹는 사람을 먼저 먹인다. 만약 먹는 시간이 같은 사람이 있다면 데우는 시간이 짧은 사람을 먼저 먹인다.  → E를 내림차순으로 정렬, 동점자에 한해서 M을 오름차순으로 정렬

이하는 코드입니다.

#include <stdio.h>
#include <queue>
 
#define MAX_N 10000
#define MAX(a ,b) (((a) > (b)) ? (a) : (b))
 
#pragma warning(disable:4996)
 
using namespace std;
 
typedef struct {
    int M;
    int E;
} LunchBox;
 
LunchBox lunchBoxes[MAX_N];
 
struct MaxCompare {
    bool operator() (const int index1, const int index2) {
        const LunchBox left = lunchBoxes[index1];
        const LunchBox right = lunchBoxes[index2];
 
        if (left.E == right.E) {
            return left.M > right.M;
        }
 
        return left.E < right.E;
    }
};
 
int main() {
    int T;
    scanf("%d\n", &T);
 
    while (T-- > 0) {
        int N;
        scanf("%d", &N);
 
        // get M
        int totalMTime = 0;
        for (int i = 0; i < N; i++) {
            scanf("%d", &lunchBoxes[i].M);
            totalMTime += lunchBoxes[i].M;
        }
 
        // get E and make heap
        priority_queue<int, vector<int>, MaxCompare> maxHeap;
        for (int i = 0; i < N; i++) {
            scanf("%d", &lunchBoxes[i].E);
            int *heapNode = new int;
            *heapNode = i;
            maxHeap.push(*heapNode);
        }
 
        //
        int time = 0;
        int tmpMTime = 0;
        int heapSize = maxHeap.size();
        for (int i = 0; i < heapSize; i++) {
            LunchBox top = lunchBoxes[maxHeap.top()];
 
            tmpMTime += top.M;
            time = MAX(time, top.E + tmpMTime);
 
            maxHeap.pop();
        }
 
        printf("%d\n", time);
    }
 
    return 0;
}