TIOJ 1072 . A.誰先晚餐

呃...

沒有證明隨便亂寫就AC了

題目鏈接:https://tioj.ck.tp.edu.tw/problems/1072

總之就是用Greedy跑下去就對啦
從吃最久的人先開始跑
把每道菜所需做的時間都存下來
(因為就算每個人都吃零分鐘也需要消耗做菜時間)
也就是說所需最小時間≥做菜時間
每次做完一道新菜後,再比較當前所用做菜時間加上吃飯時間(R)和之前所用最大的R
取其中大者
(也就是吃飯時間有沒有超過做下一道菜的時間)

以下為code

#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,t=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())

{

t+=pq.top().second;

r=max(r,t+pq.top().first);

}

cout<<r<<'\n';

}

}