显然有 $\mathrm{cost}(b,a)=\frac12\sum_{i=1}^n |a_i-b_i|$，所以每一个 $b_i$ 的贡献是独立的凸函数 $f_i(x)$。
我们希望找到一组 $b_i$ 满足 $\sum_{i=1}^n b_i=m$ 且 $\sum_{i=1}^n f_i(b_i)$ 最小，只需要按照 $f_i(x)$ 的斜率贪心即可。
时间复杂度 $O(nk\log k)$。
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 #371 for Problem #14433. Misread Problem
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-14 07:26:59
Last updated: 2025-12-14 07:27:04
题解
Comments
No comments yet.