9025

## 前言 昨天考试考到过了，顺便叫发题解，我的做法有两个，一个 $O(n)$，一个 $O(n\log n)$。 ### $O(n\log mn)$ 的方法——三分 当时考试时就想到了，因为这次的答案是单谷函数，可以使用三分，跟二分差不多，就是找向左走上升还是向右走更优，然后 $O(n)$ 统计一下 ......

# P9025题解 ## 简化题意 求一个值 $c$ 使得 $$\sum_{i=1}^n w_i(\left |c-p_i\right | -d_i)$$ 最小化 （注意题目中 $w_i$ 表示每移动一米需要 $w_i$ 秒） ## 思路 首先我们令选择 $c$ 位置的总用时为 $f(c)$ 显然， ......