poj 2828 Buy Tickets (线段树单点更新,逆序插入)

poj 2828 题目链接

题意:n个人,每个人有一个rp值(用来区分不同的人),还有一个pos[i],表示当第i个人来排队的时候插入到第pos[i]个人的后面(也就是排在位置pos[i]+1)

现在问最后的序列,从1到n输出n个人的rp值

 

思路:第二道线段树,并不会做,看了题解。

比较关键的一点是:按照顺序的话,当后来的一个人插入到前面,那么之前很多人排好的位置将发生改变,这个代价是巨大的。

由于越后来的人越容易确定位置,因此正确的做法是倒序处理。

对于第i个人,我们把他放在从前往后数的第i个空的位置即可。

接下来需要做的就是线段树处理,线段树存储的信息是某一个区间中空位置的个数。

 

感觉是一道很好的题目,对于新手来说并不是很容易,不过理解了这道题目以后,感觉进一步理解线段树,有点开心。

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz