题解 P6067 【[USACO05JAN]Moo Volume S】

我们将 $x_i$ 从小到大排序依次考虑。 容易发现对于比 $x_i$ 小的 $x_j$ 产生贡献为 $x_i-x_j$ ，对比 $x_i$ 大的 $x_k$ 产生贡献为 $x_k-x_i$ 。 只考虑 $x_i$ 的部分，容易发现有多少数字比 $x_i$ 小 $x_i$ 产生多少正贡献， 有多少数字比 $x_i$ 大产生多少负贡献。综合起来 $x_i$ 产生的贡献为: $$x_i[i-1-(n-i)]=x_i(2i-n-1)$$ 最后因为题目比较奇葩， $i$ 和 $j$ 之间会对话两次，所以将答案乘以 $2$ 即可。 瓶颈在排序，总时间复杂度为 $O(n\log n)$ 。 代码省略。