社区讨论

优先队列应该可以卡吧?

P5688[CSP-S 2019 江西] 散步参与者 3已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@lod0b80f
此快照首次捕获于
2023/10/30 22:40
2 年前
此快照最后确认于
2023/11/05 08:58
2 年前
查看原帖
虽然本蒟蒻也是用优先队列直接碾过去了(岂不是普及水平
没有说人的位置必须不同是吧?
考虑把200000200000个人分成逆时针、顺时针两组,顺时针组的编号全部小于逆时针组。
一组逆时针的100000100000个人,初始都在同一个位置。
顺时针的一组一个人一个人来,每次恰好与逆时针组大部队在一个只容纳一人出去的出口相遇,然后它出去了,逆时针组大部队继续。
那么逆时针组每次都被迫更新下一个目的地,然后每次被抢走,继续更新。
总时间复杂度O(n2logn)O(n^2 \log n),直接T没。

回复

6 条回复,欢迎继续交流。

正在加载回复...