/ Vijos / 题库 /

银行业务

银行业务

时间限制: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

信息

ID
2249
难度
(无)
分类
模拟 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
2
上传者