2022 年北京预赛

思路

凸性指函数在平均点的值不超过相应函数值的平均。加权绝对偏差和在加权中位数处最小：左侧权重使斜率为正，右侧为负，折点处检查两侧半权重。

想法从哪来：绝对值和变量很多，直接枚举所有符号区间不可行；先观察两个稳定性质：函数是凸的，交换任意两个变量不变。将所有变量排列平均，凸性保证函数值不增加，所以至少存在一个所有变量相等的极小构型。这不是假设对称必取等，而是有明确的平均化依据。一维后按所选位数分组，每个折点是一个整数的倒数，权重还需乘该整数，不能只拿二项式系数作中位数。分段线性函数在左右斜率跨零处最小，正是加权中位数条件；最后用二项式恒等式精确求和，避免把近似小数再取整。

目标函数是凸函数，并且在任意交换变量后保持不变。先对全部变量排列取平均，把极小问题降到所有变量相等的一维情形。