/ Vijos / 题库 /

小M的业务

小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
上传者