银行业务
时间限制:1秒 内存限制:256M
【题目描述】
小H跳槽到银行当业务主管,为了提高银行窗口的办事效率,需要调查客户到银行办理业务的等待时间。
银行只有一个窗口,任何人办理业务都需要排队,如果前面有人在排队等待,后来的人只能排在队尾。
现在给出 \(n\) 个客户到达银行的时间 \(s_i\)(分钟),以及办理业务需要的时间 \(t_i\)(分钟),\(n\) 个客户按到达银行的时间依次编号为 \(1,2,…,n\),请你帮助小H 计算等待时间最长的客户编号,一个客户的等待时间为排队的时间,即他来银行到他开始办理业务的这段时间。
请你帮助小H写一个程序来完成这件事情。
【输入格式】
第一行一个整数 \(n\),表示有 \(n\) 个客户。
接下来的 \(n\) 行,每行两个整数:\(s_i, t_i\),其中第 \(i+1\) 行表示编号为 \(i\) 的客户到达银行的时间为 \(s_i\) 分钟,办理业务需要 \(t_i\) 分钟。
注意:输入数据已按到达银行的时刻排好序了,且没有同一时刻多人到达银行的情况。
【输出格式】
第一行输出最长的等待时间。
第二输出等待时间最长的客户的编号,若有多个,按编号由小到大输出,编号之间用一个空格分开。
【输入输出样例1】
Input
5
1 3
3 2
6 4
7 3
12 2
Output
3
4
【输出样例解释】
客户1第1分钟到达银行,可立即办理业务,等待时间为0分钟;
客户2第3分钟到达银行,但客户1要第3分钟末才能办理完业务,所以客户2第4分钟才能办理业务,等待时间为1分钟;
客户3第6分钟到达银行,客户2刚好5分钟末办理完业务,所以客户3到达后可以立即办理业务,等待时间为0分钟;
客户4第7分钟到达银行,但客户3要第9分钟末才能办理完业务,所以客户4第10分钟才能办理业务,等待时间为3分钟;
客户5第12分钟到达银行,但客户4要第12分钟末才能办理完业务,所以客户5第13分钟才能办理业务,等待时间为1分钟;
所以,客户4等待时间最长,为3分钟。
【输入输出样例1】
Input
6
1 3
3 2
6 4
7 3
11 2
12 3
Output
3
4 6
【数据限制】
对于 \(100\%\) 的数据, \(1≤n≤1000\),\(1≤s≤10000\),\(1≤t≤10\)。
【来源】
Mr.he