AlgoSpot) LUNCHBOX

문제 : https://algospot.com/judge/problem/read/LUNCHBOX

첫번째 줄에는 테스트 케이스의 수

두번째 줄에는 도시락의 수가 주어지고

세번째 줄에는 도시락 별 도시락을 데우는데 걸리는 시간

네번째 줄에는 도시락 별 도시락을 먹는데 걸리는 시간이 주어진다.

이 문제에서 도시락 데우는 데 걸리는 시간은 무조건 일정합니다.(도시락을 먹기전에 데워야하기 떄문에)

그러므로 이 문제에서는 먹는 시간을 최소화하는것이 중요합니다.

이 문제의 경우 탐욕법을 이용하면 쉽게 풀수있습니다.

탐욕법을 사용하기위해서 먹는순서가 가장 오래걸리는거 부터 먹게 sorting했습니다.

#include 
#include 
#include 
using namespace std;

typedef struct {
	int ht; // 데우는시간
	int et; // 먹는 시간
}Lunch_Box;

int N;
Lunch_Box arr[10000];

int Comp(const Lunch_Box a, const Lunch_Box b) {
	return a.et > b.et; // 먹는게 가장 오래걸리는 도시락 먼저
}

int Result_Time() {
	int time = arr[0].ht; // 도시락을 다먹는데 걸리는 시간
	int eat_time = arr[0].et;

	for (int i = 1; i < N; ++i) {
		time += arr[i].ht;

		if (eat_time > arr[i].ht) {
			eat_time -= arr[i].ht;
		}else{
			eat_time = 0;
		}

		eat_time = max(eat_time, arr[i].et);
	}

	time += eat_time;

	return time;
}

int main() {
	std::ios::sync_with_stdio(false);

	int C;

	cin >> C;

	while (C--) {
		cin >> N;

		for (int i = 0; i < N; ++i) { // 데우는데 걸리는 시간
			cin >> arr[i].ht;
		}

		for (int i = 0; i < N; ++i) { // 먹는데 걸리는 시간
			cin >> arr[i].et;
		}

		sort(arr, arr + N, Comp);

		cout << Result_Time() << endl;
	}

	return 0;
}