设 $f_i(M)$ 为第 $i$ 个人存活时间关于 $M$ 的函数，则这个函数是由左右两段反比例函数拼接而成的，而要求的就是每个函数作为最大值的长度，我们不妨左右分开求，最后合并。求右边时，从左向右加入函数，每个函数都会取代当前的一段前缀，用栈维护即可。合并求交点时需要求解一个二次方程，注意可能退化为一次方程。时间复杂度$O(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 #242 for Problem #12307. Battle Royale
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-13 00:27:04
Last updated: 2025-12-13 00:27:12
题解
Comments
No comments yet.