f631 - 同學會
題目描述
題目描述了一個同學會的用餐情境。已知 N 位同學的初始金額，以及 M 道菜的價格。每道菜由當時最富有同學支付，如果最富有同學的金額不足，則由依次較富有的同學補足。如果所有同學的總金額不足支付所有菜餚，則輸出 "Oh My God"。題目要求輸出最初最富有同學的金額，以及用餐結束後最富有同學的金額。
解題思路
本題可以使用優先佇列 (priority queue) 來模擬同學的財產狀況。優先佇列按照同學的財產從大到小排列。對於每一道菜，從優先佇列中取出最富有同學的財產，如果該同學的財產足夠支付菜餚費用，則扣除費用後將剩餘財產放回優先佇列。否則，將該同學的財產設為 0 並放回優先佇列，然後繼續從優先佇列中取出下一位同學的財產，直到支付完菜餚費用或所有同學的財產都用完。如果在支付過程中發現所有同學的財產總和不足支付菜餚費用，則輸出 "Oh My God"。最後，輸出最初最富有同學的金額和用餐結束後最富有同學的金額。
複雜度分析
- 時間複雜度: O(N log N + M log N)
- 空間複雜度: O(N)
程式碼
#include <iostream>
#include <queue>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n,m,t;
while(cin >> n >> m){
priority_queue <int> a;
int mn=0,s=0;
for(int i=0;i<n;++i){
cin >> t;
a.push(t);
}
mn=a.top();
while(m--){
cin >> t;
while(t&&!s){
if(a.top()>=t){
int tmp=a.top()-t;
t=0;
a.pop();
a.push(tmp);
}
else{
t-=a.top();
a.pop();
a.push(0);
}
if(a.top()==0&&t)
s=1;
}
}
if(s)
cout << "Oh My God\n";
else
cout << mn << " " << a.top() << "\n";
}
}