c++) 알고스팟 - 도시락 데우기 (greedy)

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

algospot.com :: LUNCHBOX

도시락을 데우는 시간과 먹는 시간이 각각 주어졌을 때, 어떤 순서로 데워야 가장 빠른 시간에 먹을 수 있는지 구하는

문제입니다.

 

풀이과정

도시락을 먹는데 걸리는 시간이 중요한 포인트입니다.

 

1. 각 도시락을 먹는 시간을 내림차순으로 정렬합니다.

2. 내림차순으로 정렬한 도시락들을 (데우는데 걸리는 시간 누적 + 해당 도시락을 먹는 시간) 의 값을 비교하면서

가장 큰 값이 답이 될 것입니다.

 

 

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int C;
// 도시락의 수, 데우는 시간, 먹는 시간
int n;
int heating[10001];
int eating[10001];

int solution() {
    // 어느순서로 데우는지 정한다
    vector < pair <int,int > > order;
    for(int i=0; i<n; i++)
        order.push_back({-eating[i],i});
    sort(order.begin(),order.end());

    int ret = 0, beginEat = 0;
    for(int i=0; i<n; i++) {
        int box = order[i].second;
        beginEat += heating[i];
        ret = max(ret, beginEat + eating[box]);
    }
    return ret;
}

int main()
{
    scanf("%d",&C);
    for(int i=0; i<C; i++) {
        scanf("%d",&n);
        for(int j=0; j<n; j++)
            scanf("%d",&heating[j]);
        for(int j=0; j<n; j++)
            scanf("%d",&eating[j]);
        printf("%d\n",solution());
    }
}