题目描述

在整个太阳系都很有名的赌场 Galaxy Luck 推出了一种新的纸牌游戏。

在这个游戏中，有一副由 $n$ 张牌组成的牌堆。每张牌上写有 $m$ 个整数。$n$ 位玩家各自从牌堆中获得一张牌。

然后所有玩家两两对局，每一对玩家恰好对局一次。
例如，如果总共有 $4$ 位玩家，那么会进行 $6$ 场对局：

• 第 $1$ 位对第 $2$ 位
• 第 $1$ 位对第 $3$ 位
• 第 $1$ 位对第 $4$ 位
• 第 $2$ 位对第 $3$ 位
• 第 $2$ 位对第 $4$ 位
• 第 $3$ 位对第 $4$ 位

每一场对局都会产生一位获胜者，获胜者将从奖池中获得一定数量的筹码。
假设第一个玩家的牌为 $a_1,a_2,\dots ,a_m$，第二个玩家的牌为 $b_1,b_2,\dots ,b_m$，
那么获胜者获得的筹码数量为：

$$|a_1-b_1|+|a_2-b_2|+\cdots +|a_m-b_m|$$

其中 $|x|$ 表示 $x$ 的绝对值。

为了确定奖池的大小，我们需要计算所有对局中获胜者总共获得的筹码数。 由于牌的数量和玩家数可能非常大，现在请你编写一个程序完成这个计算。

输入格式

输入包含多组测试数据。

第一行输入一个整数 $t$ $(1\le t\le 1000)$，表示测试数据的组数。

对于每组测试数据：

• 第一行包含两个整数 $n,m$ $(1\le n\cdot m\le 3\times 10^5)$，分别表示牌的数量和每张牌上的数字个数。
• 接下来 $n$ 行，每行包含 $m$ 个整数 $c_{i,j}$ $(1\le c_{i,j}\le 10^6)$，表示第 $i$ 张牌上的数字。

保证所有测试数据中 $n\cdot m$ 的总和不超过 $3\times 10^5$。

输出格式

对于每组测试数据，输出一个整数，表示所有对局中获胜者获得的筹码总数。

样例输入

3
3 5
1 4 2 8 5
7 9 2 1 4
3 8 5 3 1
1 4
4 15 1 10
4 3
1 2 3
3 2 1
1 2 1
4 2 7

样例输出

50
0
31

---

说明/提示

样例 1

三张牌：

• 玩家 1：$[1,4,2,8,5]$

• 玩家 2：$[7,9,2,1,4]$

• 玩家 3：$[3,8,5,3,1]$

• 玩家 1 对 玩家 2： $|1-7|+|4-9|+|2-2|+|8-1|+|5-4|=19$

• 玩家 1 对 玩家 3： $|1-3|+|4-8|+|2-5|+|8-3|+|5-1|=18$

• 玩家 2 对 玩家 3： $|7-3|+|9-8|+|2-5|+|1-3|+|4-1|=13$

总和为 $19+18+13=50$。

提交链接

Playing in a Casino

思路分析

题目大意

在赌场里有一个游戏：

• 一共有 $n$ 张牌，每张牌上写有 $m$ 个整数。
• 我们关心的“代价”是：对每一列数字，计算所有数对的差的绝对值之和。
• 最终答案就是所有列的代价总和。

换句话说，如果我们固定一列，里面有数字 {x1,x2,…,xn}\{x_1, x_2, \dots, x_n\}{x1​,x2​,…,xn​}，
那么这一列的贡献是：

$$\sum _{1\le i<j\le n}|x_i-x_j|$$

我们要求所有列的贡献总和。

🔎 思路分析

1. 为什么不能直接暴力

• 每列有 $n$ 个数，暴力计算所有数对差值需要 $O(n^2)$。
• 但 $n$ 可能很大（比如 $2\times 10^5$），直接计算会超时。

所以必须找到一个更快的公式。

2. 关键观察

考虑一列的数字： {x1,x2,…,xn}\{x_1, x_2, \dots, x_n\}{x1​,x2​,…,xn​}

• 对每一列，记该列为 $x_1,x_2,...,x_n$

• 列的绝对差和为： $co{l}_{sum}={\sum }_{1\le i<j\le n}|x_i-x_j|$

• 总答案为所有列的 $co{l}_{sum}$ 相加。

核心做法：

1. 先将每一列排序： $y_1\le y_2\le ...\le y_n$

2. 只统计每个数作为“较小的那个数”的贡献： $contrib(i)={\sum }_{k=i+1}^n(y_k-y_i)$

3. 每列的答案：$co{l}_{sum}={\sum }_{i=1}^{n}contrib(i)$

这样每一对 $(i,j)（i<j）$只被统计一次，不重不漏，排序保证绝对值可以直接用 $y_k-y_i$ 代替。

vector< vector<long long> >a(n + 1 , vector<long long>(m + 1));

• 使用 $n+1$ 和 $m+1$ 来方便下标从 $1$ 开始。

• $a[i][j]$ 表示第 $i$ 行第 $j$ 列的数字。

for(int j = 1; j <= m; j++)
{vector<long long>temp;long long sum = 0;for(int i = 1; i <= n; i++)  //每一列{temp.push_back(a[i][j]);sum += a[i][j];}sort(temp.begin() , temp.end());....
}

1. 对每一列收集所有元素到 $temp$。

2. 求该列元素的总和 $sum$。

3. 排序，为“贡献法”做准备，使绝对值可以直接用差计算。

long long k = 0;
for(int i = 0; i < n; i++)
{k += temp[i];cost += llabs((sum - k) - (n - i - 1) * temp[i]);
}

• $k$ 用来累加当前列已处理的前 $i$ 个数的总和。

• 对于每个位置 $i$：

  • $sum-k=$ 右边所有元素的总和。

  • $(n-i-1)\ast temp[i]=$ 当前元素与右边元素的贡献差。

• llabs(...) 是绝对值函数，累加到 $cost$。

• 本质：每个数作为较小数时，与右边每个数的差的和。

参考代码

#include <bits/stdc++.h>
using namespace std;int main()
{int t , n , m;cin >> t;while(t--){cin >> n >> m;vector< vector<long long> >a(n + 1 , vector<long long>(m + 1));//n张牌  每一张牌有m个数字for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)cin >> a[i][j];long long cost = 0;for(int j = 1; j <= m; j++){vector<long long>temp;long long sum = 0;for(int i = 1; i <= n; i++)  //每一列{temp.push_back(a[i][j]);sum += a[i][j];}sort(temp.begin() , temp.end());long long k = 0;for(int i = 0; i < n; i++){k += temp[i];cost += llabs((sum - k) - (n - i - 1) * temp[i]);}}cout << cost << endl;}return 0;
}