[HOJ] 318 - 晚餐時間

Problem : 318 - 晚餐時間

Problem：

HH是一個快餐店的老闆，現在依序來了n組客人，第i組客人有Ai個人一起來，HH很苦惱該如何準備煮菜，由於先煮後到的客人所點的菜會讓先到的客人不開心，所以HH會依序按照每一組的順序煮菜。但每一組中每個人所需要的煮菜時間與吃飯時間都不盡相同，所以HH要想辦法安排每組客人的煮菜順序，使得那組客人可以越早離開越好，這樣HH才有機會早點關店休息。

假設第一組客人進場時間為0，並且位置很多，可以容納下所有的人。

Input：

第一行有一個數字n，表示一共有n組客人，然後是n組客人的資訊。

對於每組客人，第一個數字是Ai表示第i組客人一共有幾個人，接著有Ai行，每行兩個數字Xj, Yj表示這組客人的第j個人要煮Xj單位時間，花費Yj單位時間吃飯。

限制：
保證有50%的測試資料滿足:
1≤n,Ai≤500

保證所有的測試資料滿足:
1≤n,Ai≤250000
∑Ai≤250000 （客人總數在250000之內）
1≤Xj,Yj≤105

Output：

輸出n行，每行一個數字，第i行的數字表示第i組客人的離開時間。

Sample Input：

3
2
1 1
2 2
1
3 1
3
1 3
2 2
3 2

Sample Output：

4
7
14

HINT：

範例測資依照廚師煮的順序排會變成：

第幾組	第幾個客人	開始煮的時間	開始吃(煮完)的時間	吃完的時間
1	2	0	2	4
1	1	2	3	4
2	1	3	6	7
3	1	6	7	10
3	3	7	10	12
3	2	10	12	14

注意到，雖然時間3-4之間第一組客人還在吃，但是由於時間3時廚師已經將第一組兩人的餐點都煮好了，就可以開始準備下一組人的餐點了。

-----------------------------------------------------------------------------------------------------

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

struct P{

    int c,p;

}s[250005];

int cmp(P a,P b){

    return a.p > b.p;

}

int main(){

    int t,n,i,j;

    long long int maxx,now=0;

    scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        for(i=0;i<n;i++)

            scanf("%d%d",&s[i].c,&s[i].p);

        sort(s,s+n,cmp);

        maxx=now;

        for(i=0;i<n;i++){

            now+=s[i].c;

            if(now+s[i].p>maxx)

                maxx=now+s[i].p;

        }

        printf("%lld\n",maxx);

    }

}