优先队列应该可以卡吧?
查看原帖
优先队列应该可以卡吧?
10341
GK0328楼主2020/11/5 10:37

虽然本蒟蒻也是用优先队列直接碾过去了(岂不是普及水平

没有说人的位置必须不同是吧?

考虑把200000200000个人分成逆时针、顺时针两组,顺时针组的编号全部小于逆时针组。

一组逆时针的100000100000个人,初始都在同一个位置。

顺时针的一组一个人一个人来,每次恰好与逆时针组大部队在一个只容纳一人出去的出口相遇,然后它出去了,逆时针组大部队继续。

那么逆时针组每次都被迫更新下一个目的地,然后每次被抢走,继续更新。

总时间复杂度O(n2logn)O(n^2 \log n),直接T没。

2020/11/5 10:37
加载中...