[Algospot] 도시락 데우기 (문제 ID : 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.

---

왜인지 문제가 영어로 되어있으나 해석해보면 어렵지 않다. 도시락을 데우는 시간과 먹는 시간이 있을 때 모든 사람이 도시락을 다 먹는 시간을 최소화 하는 문제이다. 문제의 핵심은 먹는 시간이 오래 걸리는 사람부터 도시락을 먹는 것이다. 결국 모든 도시락을 데우는 시간은 똑같지만 마지막에 추가되는 시간은 마지막 도시락을 먹는 시간이기 때문에, 마지막에 먹는 시간이 적을수록 시간을 절약할 수 있음을 유의해서 풀면 된다. 

시간이 오래 드는 사람순으로 정렬하기 위해 order 벡터에 -를 붙여서 넣은걸 유의하자. 가장 오래 걸리는 순서 부터 도시락을 데우기 시작해서 도시락 데우는 시간을 계속 누적해가며 최대값을 최신화한다. 

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/LUNCHBOX.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int C, N;

int heat(vector<int> m, vector<int> e)
{
	vector<pair<int, int>> order;
	for (int i = 0; i < N; i++)
		order.push_back({ -e[i],i });
	sort(order.begin(), order.end());
	int res = 0, beginEat = 0;
	for (int i = 0; i < N; i++) {
		int idx = order[i].second;
		beginEat += m[idx];
		res = max(res, beginEat - order[i].first);
	}
	return res;
}

int main()
{
	cin >> C;
	while (C--) {
		cin >> N;
		vector<int> m(N);
		vector<int> e(N);
		for (int i = 0; i < N; i++) 
			cin >> m[i];
		for (int i = 0; i < N; i++) 
			cin >> e[i];
		cout << heat(m,e) << endl;
	}
}