Skip to content

11109: 【原1109】二哥买车票

题目

题目描述

author: Qiming Chen 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1109

Description

二哥被愤怒的室友追杀,于是去买火车票回老家,但是赶上了春运,买票的人排起了长队,还有很多人插队.

突然售票员起身去上厕所了,无聊的二哥就开始观察这个春运队伍的特点.

每个人有两个特性:a_i,这是他目前的任务的重要性(数字越大,说明他的事情越紧急),还有c_i,这是一个人良心.这n个人的a_i由1到n的数字不重复的排列构成.

此刻,假设队列里面有n-1个人,让我们看一看第n个人的到来会发生什么. 首先,他站在队列末尾,然后他会问前面那个人能不能插队,即执行以下操作:如果站在他前面那个人事情的重要性(a_i)没有他高,他们就会交换位置. 然后,他又会继续向前面一个人问能不能插队,依此类推.但是如果前面那个人的a_i比他的大,那他就停止他的插队工作.而且,该男子由于良心会收到谴责,最多只能插队c_n次.

假设这个排队活动中,前一个人插完队之后下一个人才来.

二哥看到这么多人插队十分蛋疼. 你的任务是帮助二哥为这个可恶的队伍做计算,当有n个人依次来排队,他们都插队结束之后,他们的顺序是什么?

有一只小鸟说这道题不能放弃...有分数拿...

Input Format

第一行是一个整数n, 表示一共有几个人陆续来排队,1<=n<=10^5,他们的编号是1~n

之后的n行每行有两个数a_i和c_i,中间用一个空格隔开,1<=a_i<=n,0<=c_i<=n

Output Format

一行,n个数中间用一个空格隔开,是这n个人的编号,从前到后表示插队结束后这n个人的顺序.

Restrictions

对于80%的数据n<=1000

对于100%的数据n<=100000

Sample Input 1

3
1 3
2 3
3 3

Sample Output 1

3 2 1

Sample Input 2

5
2 3
1 4
4 3
3 1
5 2

Sample Output 2

3 1 5 4 2

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!