[탐욕법] LUNCHBOX 도시락 데우기

1. 탐욕법 

 

이 문제는 전자레인지를 데우는 시간의 총 합은 변하지 않는다

 

이 총합과 어떤 음식하나를 다 먹는 시간 의 합의 최소값이 문제에서 구하라는 해이다.

 

점심시간을 최소화하기 위해서

 

일단 음식하나에의해 좌우 되니

 

음식 먹는 속도가 느린 사람이 제일 먼저 전자레인지를 돌릴꺼 같다.

 

2. 증명

 

만약 음식 먹는 속도가 느린사람이 첫번째로 안오는 최적해를 생각해보자

 

맨 처음 사람과 속도가 제일 느린 사람의 순서를 바꿔보자

 

순서를 바꿔도 최적해인것에는 변함이 없다.

 

그러므로 속도가 느린 사람부터 선택하는 방법은 최적해에 포함된다.

 

부분문제 또한 자명하다.

 

 

 

#include <iostream>
#include <cstring>
#include <vector>
#include <utility>
#include <algorithm>
 
 
//N <= 10000
std::vector<int> M;
std::vector<int> E;
std::vector<std::pair<int, int>> I;
 
int lunch()
{
    int sumM = 0;
    int sumME = 0;
    
    for(; 0 != I.size();)
    {
        sumM += I.back().second;
        
        if(sumM + I.back().first > sumME)
            sumME = sumM + I.back().first;
        I.pop_back();
    }
    return sumME;
 
}
 
int main()
{
    int testCase = 0;
    int N = 0;
    
    std::cin>>testCase;
    for (int i = 0; i < testCase; i++)
    {
        M.clear();
        E.clear();
        I.clear();
        std::cin>>N;
        for (int j = 0; j < N; j++)
        {
            int tmp;
            std::cin>>tmp;
            M.push_back(tmp);
        }
        for (int j = 0; j < N; j++)
        {
            int tmp;
            std::cin>>tmp;
            E.push_back(tmp);
        }
        for(int j = 0; j < N; j++)
            I.push_back(std::make_pair(E[j], M[j]));
        std::sort(I.begin(), I.end());
        std::cout<<lunch()<<"\n";
    }
}

LUNCHBOX