After graduating from Dali High School 20 years ago, the class leader at the time, Biao, decided to hold a reunion dinner this year. Everyone has the opportunity to gather again, enjoy drinks, and chat freely.
A total of N classmates attended the event, and a total of M dishes were served. Before the dinner, everyone agreed that each dish served, would be paid by the classmate with the highest amount of money present at that time. If the wealthiest classmate doesn't have enough money, then the next wealthiest classmate would pay the remaining amount, and so on.
Of course, if the total amount of money among all classmates is not enough to cover the cost of all the dishes, well, that would be embarrassing!
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| EOF input (up to 100 sets), each set consisting of 3 lines.
The first line contains two integers N and M (1 <= N, M <= 10,000). The second line contains N integers, representing the initial amount of money each student carries. The third line contains M integers, representing the amount of money each dish costs. | For each test case, output one line containing two integers: the initial amount of money the richest student has and the amount of money the richest student has after the meal. If there is not enough money to pay for the dishes, output "Oh My God". |
| 3 4 100 200 300 200 200 200 200 5 7 1500 1500 1000 2000 3000 900 600 200 350 1200 400 1000 | Oh My God 3000 1450 |
Thought Process
You can use a priority queue to store the amount of money each person has. When storing data, you can use .push(amount) to insert the amount into the priority queue. When retrieving data, you can use .top() to return the current maximum value.
Using a while loop, if the current maximum amount can be paid for the current dish, subtract the dish price from the maximum amount. You shouldn't directly modify the top element of the priority queue (top()), so you can store it in a variable, subtract the dish price from it, and then use pop() to remove the maximum value from the priority queue. After that, you can push the updated value back into the priority queue.
If the maximum amount is not sufficient to pay for the dish, you can set the variable to zero, subtract the maximum amount from the current dish price, and continue the while loop.
You can set a boolean variable to determine whether to output "Oh My God". If it's determined that there's not enough money to pay for the dishes, you can set this variable to true, and then in the subsequent for loop, if this variable is true, you can continue to the next iteration without performing any further calculations.
Sample Code－ZeroJudge F631: Classmates
#include <iostream>
#include <queue>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N, M;
while (cin >> N >> M)
{
priority_queue<int>num;
for (int i = 0; i<N; i++)
{
int tmp;
cin >> tmp;
num.push(tmp);
}
int first = num.top();
bool god = false;
for (int i = 0; i<M; i++)
{
int tmp, count = N-1;
cin >> tmp;
if (god) continue;
while (count >= 0)
{
if (num.top() >= tmp)
{
int t = num.top();
t -= tmp;
num.pop();
num.push(t);
tmp = 0;
break;
}
tmp -= num.top();
num.pop();
num.push(0);
count--;
}
if (tmp > 0) god = true;
}
if (god) cout << "Oh My God\n";
else cout << first << " " << num.top() << "\n";
}
}
//ZeroJudge F631
//Dr. SeanXD