题目大意是路上有很多石头,当你遇到奇数序列的石头就把他向前仍,偶数的不动他,如果两个石头一起,先考虑可以仍的比较近的石头仍也就是比较大的石头,这样一直下去,直到前面所有的石头都不可以仍了为止,求最远的石头距离起点多少题目这题用优先队列非常方便.
分析;可以定义一个结构体,分别存储石头现在的位置和能能出去的距离到优先队列中,然后每次取“最小的”,如果取得是偶数个就不动,取得是奇数个就要更新该石头的位置并重新存到优先队列中,直到队列空,输出最后一个石头的位置
数据分析:程序的时间复杂度是O(nlogn),数据量最大为100,000,不会超时。要特别注意多个石头的x一样的情况,要优先考虑y值最小的那块石头
1 |
|