Microwaving Lunch Boxes - 하
문제
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
입출력 예
1
2
3
4
5
6
7
8
9
10
11
12
// Input
2
3
2 2 2
2 2 2
3
1 2 3
1 2 1
// Output
8
7
풀이
- Greedy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
bool comp(std::pair<int,int>& a, std::pair<int,int>& b){
return a.first > b.first;
}
int solution(int n, std::vector<int>& heating, std::vector<int>& eating){
unsigned int time = 0, vecSize = heating.size();
std::vector<std::pair<int,int>> sch;
std::vector<int> reaminEat(eating);
for(auto i = 0 ; i < vecSize ; ++i){
sch.push_back(std::make_pair(eating[i], heating[i]));
}
std::sort(sch.begin(), sch.end(), comp);
for(auto i = 0; i < vecSize ; ++i){
time += sch[i].second;
int sum = 0;
for(auto j = i+1 ; j < vecSize ; ++j){
sum += sch[j].second;
}
int remainTime = sch[i].first - sum;
reaminEat[i] = remainTime <= 0 ? 0 : remainTime;
}
return time + *std::max_element(reaminEat.begin(), reaminEat.end());
}