题解：P9288 [ROI 2018] Innophone

keatsli · 2024-09-17 14:50:34 · 题解

我们充分发扬人类智慧：

对于每一个 a=x_t 从小到大考虑，用 vector 暴力 insert 维护剩余的 y。

凭借数学直觉，答案关于 b 的函数非常单峰。

所以我们直接爬山，只取爬到答案附近 600 个点的 max。

这样速度快得飞起，最慢的点也只要 669ms。