題目描述

在整個太陽系都很有名的賭場 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|+?+|a_m?b_m|$$

其中 $|x|$ 表示 $x$ 的絕對值。

為了確定獎池的大小，我們需要計算所有對局中獲勝者總共獲得的籌碼數。 由于牌的數量和玩家數可能非常大，現在請你編寫一個程序完成這個計算。

輸入格式

輸入包含多組測試數據。

第一行輸入一個整數 $t$ $(1\le t\le 1000)$，表示測試數據的組數。

對于每組測試數據：

• 第一行包含兩個整數 $n,m$ $(1\le n?m\le 3\times 10^5)$，分別表示牌的數量和每張牌上的數字個數。
• 接下來 $n$ 行，每行包含 $m$ 個整數 $c_{i,j}$ $(1\le c_{i,j}\le 10^6)$，表示第 $i$ 張牌上的數字。

保證所有測試數據中 $n?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)?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;
}