当玩家一有多个相同的 $a$ 时，最坏情况下一定是选择 $b$ 最大的。所以我们可以按 $(a,b)$ 从大到小排序，玩家二取得的第 $k$ 个数一定排在第 $2k$ 位或以后，确定要选哪些数之后只需要从前往后选即可。所以可以从后往前扫，用堆维护可以选的数，每次遇到可以选的位置就取当前堆中的最大值。也可以把所有数从大到小排序后用并查集维护可以选的位置，贪心选择。
时间复杂度 $O(n\log n)$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #142 for Problem #7231. Greedy game
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-12 23:31:06
Last updated: 2025-12-12 23:31:10
题解
Comments
No comments yet.