普及⏱ 1000ms💾 256MB#P5052🏷️ 贪心

题目描述

$n$ 个任务,第 $i$ 个需要 $t_i$ 时间、截止时间为 $d_i$。同一时刻只能做一个任务,任务必须完整连续地执行(中间不能暂停),从时刻 $0$ 开始按某个顺序执行。总延误定义为每个任务的完成时刻超过其截止时间的部分之和(未超时记 $0$)。最优执行顺序为:按截止时间 $d_i$ 升序执行,截止时间相同的按输入编号升序。输出该执行顺序的任务编号。

输入格式

第一行整数 $n$;接下来 $n$ 行每行两个整数 $t_i, d_i$。

输出格式

一行 $n$ 个整数:按执行顺序的任务编号。

数据范围

$$1 \le n \le 1000,\ 1 \le t_i \le 100,\ 0 \le d_i \le 10^9$$

样例输入 #1
4
9 18
8 8
7 6
2 10
样例输出 #1
3 2 4 1
样例输入 #2
6
5 20
6 7
6 10
9 11
3 22
6 11
样例输出 #2
2 3 4 6 1 5