CF1808B Playing in a Casino 题解

InversionShadow · 2023-04-28 07:24:20 · 题解

CF1808B Playing in a Casino 题解

思路：

题目求的是 \sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\sum\limits_{k=1}^m|c_{i,j}- c_{j,k}|。

一列一列单独处理。

将一列的数值排序后，算每个数字和在它前面的数字的贡献。因为一对数只算一次，所以我们考虑到大的数字的时候再算这一对，这样能把外面的绝对值符号去掉。

对于 a_i 需要算 a_i-a_{i-1}+a_i-a_{i-2}+\dots + a_i-a_1，即 (i-1)\times a_i-sum_{i-1}。