小M的业务
时间限制:1秒 内存限制:256M
【问题描述】
小M跳槽到银行当业务主管,为了提高银行窗口的办事效率,需要调查客户到银行办理业务的等待时间。
银行只有一个窗口,任何人办理业务都需要排队,如果前面有人在排队等待,后来的人只能排在队尾。现在给出 \(n\) 个客户到达银行的时间 \(s\)(分钟),以及办理业务需要的时间 \(t\)(分钟), \(n\) 个客户按到达银行的时间依次编号为 \(1,2,…,n\),请你帮助小 M 计算等待时间最长的客户编号,一个客户的等待时间为排队的时间,即他来银行到他开始办理业务的这段时间。
请你帮助小M写一个程序来完成这件事情。
【输入格式】
第1行一个整数 \(n\),表示有 \(n\) 个客户。接下来的 \(n\) 行,每行两个整数:\(s t\),其中第 \(i+1\) 行表示编号为 \(i\) 的客户到达银行的时间为 \(s\) 分钟,办理业务需要 \(t\) 分钟。
注意:输入数据已按到达银行的时刻排好序了,且没有同一时刻多人到达银行的情况。
【输出格式】
第 1 行输出最长的等待时间。
第 2 输出等待时间最长的客户的编号,若有多个,按编号由小到大输出,编号之间用一个空格分开。
【输入输出样例1】
Input
5
1 3
3 2
6 4
7 3
12 2
Output
3
4
【输入输出样例1解释】
客户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分钟。
【输入输出样例2】
Input
6
1 3
3 2
6 4
7 3
11 2
12 3
Output
3
4 6
【数据限制】
\(1≤n≤1000\)
\(1≤s≤10000\)
\(1≤t≤10\)
【来源】
Mr.he
信息
- ID
- 1037
- 难度
- 4
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 被复制
- 2
- 上传者