本文从WordPress迁移而来, 查看全部WordPress迁移文章
线段树
题意:输入n有n个人排队,下面n行,每行第1个数字表示这个人想插队的位置(那个数字表示他插入后他前面有多少人,如果是0的话说明他插入后他是第1位,他前面没人),后面那个数字只是个标号,相当于他的名字吧,你要输出n个人插队后,队伍的状态,从头到尾输出那些人的名字
这题要从后面考虑,最后那个人,他插完队了,那么他的位置是固定的,就在那里,可见他不受前面任何一个人的影响。看看倒数第2个人,其实他插入的位置是有可能受到倒数第1个人的影响的,但是不受前面任何人的影响。逆回来插入人,看看他要位于哪个位置p(0即位于第一位,1即位于第二位………),然后从第1个位置开始数,数到第p个空位置(注意是空的才计数),那么就是他最后插入的地方。
所以线段树要维护的信息就是,一个区间内有多少空位置,对于一个人准备插入的时候,就是在总区间[1,n]内找到第p个空位置,然后插入,标记这个位置为占用了
用G++提交超时…………..
1 |
|
其实问题就是每次都要找出第x个空位,这是可以用树状数组去实现的,用的是一种二分逼近的思想(和二分不同)
1 |
|