algospot LUNCHBOX

문제 링크입니다: https://algospot.com/judge/problem/read/LUNCHBOX

데우는 시간은 상관이 없고 먹는 시간이 식사시간을 좌지우지한다는 것이 핵심이였습니다.

/*

유명한 도시락 업체에서 n개의 도시락을 주문했다.

주문량이 많아서 한가지 도시락만 주문할 수는 없었기 때문에 여러가지 종류의 도시락을 주문했다.

하지만 전자레인지는 하나뿐이고 출력량도 적어 한번에 한 도시락만 데울 수 있다.

이 때, 식사시간을 최소화 하려면 어떻게 해야할까?

*/

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

const int MAX = 10000; //boxNum<=10000

int boxNum;

int heating[MAX], eating[MAX];

 

int microwave(void)

{

        //어느 순서로 데워야할지를 정한다

        vector<pair<int, int>> order;

        for (int i = 0; i < boxNum; i++)

               order.push_back(make_pair(-eating[i], i));

        //도시락 먹는데 걸리는 시간 역순

        //즉, 오래 먹는 순서부터

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

        //해당 순서대로 데워먹는 과정을 시뮬레이션

        int result = 0, beginEat = 0; //결과, 먹기 시작한 시간

        for (int i = 0; i < boxNum; i++)

        {

               int box = order[i].second;

               beginEat += heating[box];

               result = max(result, beginEat + eating[box]);

        }

        return result;

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case < 1 || test_case>300)

               exit(-1);

       

        for (int i = 0; i < test_case; i++)

        {

               cin >> boxNum;

               //데우는데 걸리는 시간

               for (int j = 0; j < boxNum; j++)

                       cin >> heating[j];

               //먹는데 걸리는 시간

               for (int j = 0; j < boxNum; j++)

                       cin >> eating[j];

               cout << microwave() << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략