AcWing 105. 七夕祭(Java)
原题链接
困难
作者:
peilin
,
2020-06-20 09:22:25
,
所有人可见
,
阅读 833
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int T = sc.nextInt();
int[] row = new int[N];
int[] col = new int[M];
for(int i = 0; i < T; i++) {
row[sc.nextInt() - 1]++;
col[sc.nextInt() - 1]++;
}
if(T % N == 0 && T % M == 0) {
long rowSwapNum = getNumOfSwap(T/N, N, row);
long colSwapNum = getNumOfSwap(T/M, M, col);
System.out.println("both " + (rowSwapNum + colSwapNum));
} else if(T % N == 0) {
long rowSwapNum = getNumOfSwap(T/N, N, row);
System.out.println("row " + rowSwapNum);
} else if(T % M == 0) {
long colSwapNum = getNumOfSwap(T/M, M, col);
System.out.println("column " + colSwapNum);
} else {
System.out.println("impossible");
}
}
private static long getNumOfSwap(int avg, int len, int[] array) {
long[] sum = new long[len];
sum[0] = array[0] - avg;
for(int i = 1; i < len; i++) {
sum[i] = sum[i - 1] + (array[i] - avg);
}
Arrays.sort(sum);
long mid = sum[len / 2];
long numOfSwap = 0;
for(int i = 0; i < len; i++) {
numOfSwap += Math.abs(sum[i] - mid);
}
return numOfSwap;
}
}