‹ 上一题 下一题 ›

s09189. 退定金划算吗 未做

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

题目描述

手作工作室接了 张预售订单,编号 。工作室每天恰好完成一张订单,排产流程固定如下:

  1. 把订单按交付期升序排列,交付期相同的按编号升序;
  2. 逐单入选:订单先进入保留集合;若保留集合中的订单数超过该订单的交付期,退掉一张订单——即退还定金:退集合中定金最低的一张(定金相同时退编号最小的),退单计数加一;
  3. 流程跑完后,输出退单总次数;一次都没退则输出 。

你的任务是实现这套流程,输出退单总次数。

输入格式

第一行一个整数 。

接下来 行,第 行两个整数 :交付期与定金(输入顺序任意)。

输出格式

一行一个整数:退单总次数。

样例 1

样例

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

排序后处理顺序为 :入选编号 (交付期 )时保留数 超过 ,退掉定金最低的编号 (定金 ,刚入选即被退)。此后无超限,共退 次。

样例 2

排序后依次入选,保留数 均未超过对应交付期 ,一次都没退。

数据范围

;;。

输入
输出

            
答案