‹ 上一题 下一题 ›

s09187. 截止收益调度 未做

1000 ms 256 MB 测试点 10 通过率 33% S-06·贪心进阶与反悔贪心反悔贪心

题目描述

货运站收到 笔发运订单。发运口按时段发货:时段 ,每个时段恰好发运一笔订单。第 笔订单若在时段 或更早发运,站里赚到利润 ;放弃则不赚。

调度员的排单流程固定如下:

  1. 把订单按截止时段升序排列,截止相同的按输入编号升序;
  2. 逐笔入选:订单先进入保留集合;若保留集合中的订单数超过当前订单的截止时段,退掉集合中利润最低的一笔(利润相同时退编号最小的);
  3. 流程结束后,保留集合即最终发运方案。

输出最终发运方案的总利润与发运订单数。其中总利润等于所有不超期方案中利润总和的最大值。

输入格式

第一行一个整数 。

接下来 行,第 行两个整数 。

输出格式

两行:第一行总利润;第二行发运订单数。

样例 1

样例

输入
4
1 3
1 6
2 8
3 5
输出
19
3

按流程处理顺序为 :入选编号 (截止 )时保留数 超过 ,退掉利润最低的编号 (利润 );此后无超限。最终保留 ,利润 ,发运 笔。

样例 2

排序后处理顺序为 :入选编号 时退编号 (利润并列 ,编号小的先退);入选编号 时退编号 ;入选编号 时刚入选的编号 (利润 )自己被退。最终保留 ,利润 ,发运 笔。

数据范围

;;。总利润可能超过 位整数范围。

输入
输出

            
答案