# TIOJ 誰來三餐-題解
## TIOJ-1072 A.誰來晚餐
**Description:**
經過了一整天漫長難熬的上課時間之後，期待了一整天下課的小尹終於能夠暫時逃離課業的轟炸，回到他最喜歡的休閒活動 － 楓之谷的懷抱了！正當小尹迫不及待的連上網路準備大展身手之時，肚子卻不聽使喚的抗議的起來，於是他只好決定先去飽餐一頓回來，晚上才有力氣好好廝殺。
一陣呼朋引伴之後小尹和他的同學們來到了最近的小吃店，每個人選好了菜單上自己想要吃的餐點，正準備要把菜單遞給老闆的時候，小尹卻突然叫大家停了下來，他說：「你看哦，我們有人吃飯快有人吃飯慢，每道菜煮好送上來的時間也不一樣。如果我先吃完，還要等你們吃，又不想拋棄你們自己先回去。那麼如果老闆送菜順序不對的話，我就可能要等很久才能回去玩。最好是我們自己先想好理想的上菜順序，告訴老闆請他照著順序煮菜，才能讓我們大家一起早點回去玩，這樣好不好？」
超有行動力的小尹馬上就開始收集這家小吃店的資訊。他發現這家店很不幸的只有一組廚具，而每份餐點都必須分開來煮，一道煮完才能煮另外一道。而且菜單上每份餐點也都有不同的烹煮時間：例如蛋炒飯可能很快就好了，水餃因為要現包就要等久一點。同時小尹也調查了大家吃飯的速度，估算出每個人吃他所點的餐所需要的時間 (我們假設每個人只有點一份餐)。每份餐點煮好了之後會馬上上桌且立即可食用，而老闆也可以同時緊接著煮下一道菜。小尹身為一個資訊系的學生，有了這些資料之後二話不說就拿出了電腦，想要寫個程式來解決這個問題，可是一時之間卻好像想不到理想的解法。你能幫小尹想個辦法，讓他盡可能早點回到楓之谷的世界嗎？
---
| Input Format | Output Format |
| -------- | -------- |
| 輸入檔包含多組測試資料，每一組測試資料的第一行有一個整數N (1 ≤ N ≤ 10000)，代表跟小尹去吃飯的人數，接下來的N行每行有兩個以空白字元分隔的整數Ci Ei ( 1 ≤ i ≤ N, 1 ≤ Ci, Ei ≤ 1000)，其中Ci代表烹煮第i個人點的餐點所需要的時間，Ei代表第i個人把他點的餐點吃完所需要的時間。讀到N = 0的時候代表測試檔案的結尾，不需要對於這個數字作任何輸出。 | 對於每一組測試檔，輸出一個正整數在一行內，代表「從老闆開始煮第一道餐點開始，到最後一個人吃完為止，中間一共花了多少時間」，這個數字應該越小越好。 |
---
Sample Input:
3
1 1
2 2
3 3
0
Sample Output:
7
---
**AC code:**
想法:Greedy、Priority_queue基本運用
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define AC ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int main()
{
AC
ll n;
while(cin>>n&&n)
{
ll c,e,r=0,total=0;
priority_queue<pair<ll,ll>> pq;
for(ll i=0;i<n;i++)
{
cin>>c>>e;
pq.push(make_pair(e,c));
}
for(;pq.size();pq.pop())
{
total+=pq.top().second;
r=max(r,total+pq.top().first);
}
cout<<r<<'\n';
}
return 0;
}
```
## TIOJ-1440 誰買早餐
**Description:**
還記得NPSC2005的誰先晚餐以及2007的誰來午餐嗎？
不過這題是誰買早餐。
由於培訓的時間過早，所以大多數參加的人都沒有吃早餐就來參加培訓了。
基於大家的辛勞以及儲備大家的體力，老師決定請大家吃早餐。
但因為每個人的體重不一樣，所以營養需求量也不一樣，一定要吃到營養含量不比自己的需求量低的早餐才能滿足。
老師一大早興沖沖的跑到了早餐部，卻發現每種早餐的營養含量以及價錢都不大一樣，營養越高價錢越高，而且都只剩下一份。
這下老師傷腦筋了，因為他帶的錢並不多，所以他希望花最少錢滿足大家的營養需求量。
（注意：由於公平的問題，每個人只能吃一份早餐）
---
**Input Format && Sample Input**
本題只有一筆測資：
第一行包含一個正整數 n ，代表參加培訓的人數（0 < n <= 1000000）
接下來有 n 行，每行有一個數字 ai，代表每人的營養需求量
第 n+2 行有一個正整數 m ，代表早餐種類的數量（0 < m <= 1000000）
接下來有 m 行，每行有兩個數字bi、ci，代表每份早餐的營養含量以及價錢。
*輸入如下*:
2
5
4
3
7 7
8 8
4 4
**Output Format && Sample Output**
請輸出老師最少要花多少錢，才能滿足大家的營養需求。（我們保證答案在long long int的範圍內）
若無法滿足，請輸出"Impossible."（不含雙引號）
*輸出如下:*
11
---
**AC Code:**
想法:Greedy基礎
```cpp=
#include <bits/stdc++.h>
#define AC ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define s second
#define f first
#define pb push_back
typedef long long int ll;
using namespace std;
bool cmp(pair<ll,ll> k,pair<ll,ll> l) {
return k.s<l.s;
}
int main() {
AC
ll n,m,cnt=0,a,b,c;
vector<pair<ll,ll>> food;
vector<ll> student;
cin>>n;
for(ll i=0;i<n;i++) {
cin>>a;
student.push_back(a);
}
cin>>m;
for(ll i=0;i<m;i++) {
cin>>b>>c;
food.push_back({b,c});
}
sort(student.begin(),student.end());
sort(food.begin(),food.end(),cmp);
ll now=0,money=0;
for(ll i=0;i<m;i++) {
if(food[i].f>=student[now]) {
money+=food[i].s;
now++;
if(now>=n) break;
}
}
if(now<n) cout<<"Impossible.\n";
else cout<<money<<'\n';
return 0;
}
```
## TIOJ-1485 誰來午餐
Sign in with Wallet
Connect another wallet