题解：P12532 [XJTUPC 2025] Primal Core Optimization: Attribute Balance

给个不同的观察。

考虑题目涉及到的函数 $L(x,y,z) = \max(x,y,z,0)-\min(x,y,z,0)$，它满足下列条件：

正定性：

$L(x,y,z,0) \ge 0$，当且仅当 $x=y=z=0$ 时取等。

绝对一次齐次性：

$L(ax,ay,az,0) = |a|L(x,y,z,0)$，这要分 $a$ 的正负证明：

$a\ge 0$ 是平凡的，此时：

$a < 0$ 时：

三角不等式：

我们记 $M_i=\max(x_i,y_i,z_i,0)$，$m_i=\min(x_i,y_i,z_i,0)$，则 $L(x_i,y_i,z_i) = M_i - m_i$。

另记 $M_{12} = \max(x_1+x_2,y_1+y_2,z_1+z_2,0)$，$m_{12} = \min(x_1+x_2,y_1+y_2,z_1+z_2,0)$，则有：$L(x_1+x_2,y_1+y_2,z_1+z_2)=M_{12} - m_{12}$。

由于 relu 函数 $\max(a,0)$ 显然有性质 $\max(a,0)+\max(b,0) \ge \max(a+b,0)$，不难推广到：

同理，因为 $\min(a,0)$ 满足 $\min(a,0)+\min(b,0) \le \min(a+b,0)$，可以推广到：

所以会有：

由于 $L(x,y,z)$ 满足上面三个性质， $L$ 成功升格为 $\mathbb R^3$ 空间上的一个范数。我们记作 $\Vert\cdot\Vert_L$。

那么 $(\mathbb R^3,+, \Vert\cdot\Vert_L)$ 就是一个赋范线性空间。

这个范数可以诱导一个度量：$d(\mathbf u,\mathbf v) = \Vert \mathbf u - \mathbf v\Vert_L$。$(\mathbb R^3, d)$ 就是一个度量空间。

这时候，我们想知道的凸性什么的都已经是代数里的基本结论了。

而且，不难发现题目要求等价如下：

如果是 $L_2$ 范数，结论是取 $\bf x_i$ 平均值；如果是 $L_1$ 范数，结论是取 $\bf x_i$ 每坐标分别的中位数。

由于所有范数在拓扑上的等价性，可以考虑一些乱搞做法：初值选在平均值或中位值，然后用一些一阶优化算法（梯度下降什么的）或者零阶优化算法（模拟退火、爬山什么的）。