题解：P12914 [POI 2020/2021 R2] 沙滩游客 / Plażowicze

Little_corn · 2025-11-11 07:54:43 · 题解

没搞懂难点和细节在哪？

首先题意写的比较清楚了，每次找长度最大的段分裂成两段相同长度的相邻段。暴力 O(k) 是容易的。考虑将原段分裂出来的段一起考虑，则不难发现你只会考虑 O(n \log k) 个原段，这是因为你每次相当于令 2^c \to 2^{c+1}, k \gets k - 2^c，c 为该原段断出来的段数。直接使用 pq 模拟该过程即可 O(n \log k \log n)。非常好写，场上 30min 写 + 调。