#P17859. [XV Open Cup]Analyze This
[XV Open Cup]Analyze This
题目描述
一家餐厅有 位顾客,第 位顾客每天在时刻 到达。每天的餐点制作时间相同,但不同天可能不同。
某天制作一份餐点需要 分钟。每位顾客到达后立即点餐,在时刻 取餐并离开。餐厅可以同时处理任意多个订单。
顾客到达时,会与店主以及所有尚未离开的顾客握手。若一位顾客恰好在此时离开,两人仍会握手。已经在店内的顾客与新顾客握手时,他的愤怒值等于自己已经等待的分钟数。店主的愤怒值始终是 。
给定 天的制作时间 ,请分别找出一次能产生当天最大愤怒值的握手,输出参与握手的两个人的编号。顾客按输入顺序编号为 到 ,店主编号为 。
等价地,若选出两个不同顾客 ,必须满足 ,产生的愤怒值为 ;店主与任意顾客握手产生的愤怒值为 。你需要使这个值最大。
输入格式
第一行包含两个整数 。
第二行包含 个整数 。到达时间不保证有序,也可能相同。
接下来 行,每行包含一个整数 。
输出格式
输出 行。第 行输出两个不同的人的编号 ,表示第 天选出的握手。两人的顺序任意;若有多个最优答案,输出任意一个。
数据范围
- ;
- ;
- 。
样例
3 4
1 2 5
0
5
1
3
0 1
1 3
1 2
2 3
样例解释
四天能产生的最大愤怒值依次为 。