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了,可以的话,请您参考添加页面,与大家一起分享你的题解!