Skip to Content
CTRL K

Playing in a Casino

Análisis oficial (C++) 

Explicación

El problema pide calcular la suma de diferencias absolutas ∑i<j∣ai−aj∣\sum_{i < j} |a_i - a_j| a través de las MM cartas para NN jugadores. Al transponer la entrada en MM filas y NN columnas, podemos aislar y ordenar de forma independiente los valores de cada carta.

Una vez ordenado, un elemento xjx_j en el índice jj actúa como el valor más grande en jj pares y como el valor más pequeño en N−1−jN - 1 - j pares en la diferencia absoluta expandida. Así, su contribución neta será: (j−(N−1−j))×xj(j - (N - 1 - j)) \times x_j.

Implementación

Complejidad temporal: O(MNlog⁡N)\mathcal{O}(MN \log N)

#include <bits/stdc++.h>
using namespace std;
 
 
int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n, m;
		cin >> n >> m;
 
		vector<vector<int>> p(m, vector<int>(n));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				// transponemos a m por n para facilitar el ordenamiento
				cin >> p[j][i];
			}
		}
 
		long long wins = 0;
		for (int i = 0; i < m; i++) {
			sort(p[i].begin(), p[i].end());
			for (int j = 0; j < n; j++) {
				// sumamos las contribuciones individuales por carta
				wins += 1ll * (j - (n - 1 - j)) * p[i][j];
			}
		}
 
		cout << wins << '\n';
	}
}
import java.io.*;
import java.util.*;
 
public class PlayingInCasino {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
 
		int testNum = Integer.parseInt(br.readLine());
		for (int t = 0; t < testNum; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
 
			int[][] p = new int[m][n];
			for (int i = 0; i < n; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < m; j++) {
					// transponemos a m por n para facilitar el ordenamiento
					p[j][i] = Integer.parseInt(st.nextToken());
				}
			}
 
			long wins = 0;
			for (int i = 0; i < m; i++) {
				Arrays.sort(p[i]);
				for (int j = 0; j < n; j++) {
					// sumamos las contribuciones individuales por carta
					wins += (long)(j - (n - 1 - j)) * p[i][j];
				}
			}
 
			pw.println(wins);
		}
		pw.close();
	}
}
for _ in range(int(input())):
	n, m = map(int, input().split())
	p = [[0] * n for _ in range(m)]
 
	for i in range(n):
		row = list(map(int, input().split()))
		for j in range(m):
			# transponemos a m por n para facilitar el ordenamiento
			p[j][i] = row[j]
 
	wins = 0
	for i in range(m):
		p[i].sort()
		for j in range(n):
			# sumamos las contribuciones individuales por carta
			wins += (j - (n - 1 - j)) * p[i][j]
 
	print(wins)
Fundamentos