fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.     // -----------------------------------------
  5.     // 1. 使用归并排序统计逆序数 (最少相邻交换次数)
  6.     // -----------------------------------------
  7.     static long mergeSortCount(int[] arr, int left, int right, int[] temp) {
  8.         if (left >= right) return 0;
  9.         int mid = (left + right) >>> 1;
  10.         long invCount = 0;
  11.         invCount += mergeSortCount(arr, left, mid, temp);
  12.         invCount += mergeSortCount(arr, mid + 1, right, temp);
  13.         invCount += merge(arr, left, mid, right, temp);
  14.         return invCount;
  15.     }
  16.  
  17.     static long merge(int[] arr, int left, int mid, int right, int[] temp) {
  18.         int i = left, j = mid + 1, k = 0;
  19.         long invCount = 0;
  20.         while (i <= mid && j <= right) {
  21.             if (arr[i] <= arr[j]) {
  22.                 temp[k++] = arr[i++];
  23.             } else {
  24.                 // arr[i] > arr[j] 表示产生了 (mid - i + 1) 个逆序
  25.                 // 因为左段从 i 开始到 mid 都比 arr[j] 大
  26.                 temp[k++] = arr[j++];
  27.                 invCount += (mid - i + 1);
  28.             }
  29.         }
  30.         while (i <= mid) {
  31.             temp[k++] = arr[i++];
  32.         }
  33.         while (j <= right) {
  34.             temp[k++] = arr[j++];
  35.         }
  36.         for (int p = 0; p < k; p++) {
  37.             arr[left + p] = temp[p];
  38.         }
  39.         return invCount;
  40.     }
  41.  
  42.     // -----------------------------------------
  43.     // 2. 获取 N×N 矩阵的顺时针螺旋遍历下标列表
  44.     // -----------------------------------------
  45.     static List<int[]> spiralOrderIndices(int N) {
  46.         List<int[]> order = new ArrayList<>();
  47.         int top = 0, bottom = N - 1;
  48.         int left = 0, right = N - 1;
  49.         while (true) {
  50.             // 从左到右
  51.             for (int col = left; col <= right; col++) {
  52.                 order.add(new int[]{top, col});
  53.             }
  54.             top++;
  55.             if (top > bottom) break;
  56.  
  57.             // 从上到下
  58.             for (int row = top; row <= bottom; row++) {
  59.                 order.add(new int[]{row, right});
  60.             }
  61.             right--;
  62.             if (right < left) break;
  63.  
  64.             // 从右到左
  65.             for (int col = right; col >= left; col--) {
  66.                 order.add(new int[]{bottom, col});
  67.             }
  68.             bottom--;
  69.             if (bottom < top) break;
  70.  
  71.             // 从下到上
  72.             for (int row = bottom; row >= top; row--) {
  73.                 order.add(new int[]{row, left});
  74.             }
  75.             left++;
  76.             if (left > right) break;
  77.         }
  78.         return order;
  79.     }
  80.  
  81.     public static void main(String[] args) {
  82.         Scanner sc = new Scanner(System.in);
  83.         // 读取 N
  84.         int N = sc.nextInt();
  85.         // 读取矩阵
  86.         int[][] matrix = new int[N][N];
  87.         for (int i = 0; i < N; i++) {
  88.             for (int j = 0; j < N; j++) {
  89.                 matrix[i][j] = sc.nextInt();
  90.             }
  91.         }
  92.  
  93.         // 生成螺旋顺序下标列表
  94.         List<int[]> spiralPos = spiralOrderIndices(N);
  95.  
  96.         // 依螺旋顺序将矩阵展成一维数组 arr
  97.         // arr 的期望排序结果应为 [1, 2, 3, ..., N^2]
  98.         int[] arr = new int[N * N];
  99.         for (int i = 0; i < spiralPos.size(); i++) {
  100.             int r = spiralPos.get(i)[0];
  101.             int c = spiralPos.get(i)[1];
  102.             arr[i] = matrix[r][c];
  103.         }
  104.  
  105.         // 利用 归并排序 统计逆序数(即最少相邻交换次数)
  106.         int[] temp = new int[arr.length];
  107.         long inversions = mergeSortCount(arr, 0, arr.length - 1, temp);
  108.  
  109.         // 输出结果
  110.         System.out.println(inversions);
  111.     }
  112. }
  113.  
Success #stdin #stdout 0.18s 54544KB
comments (?)
stdin
copy 
2
3 1
2 4
stdout
copy 
3
https://ideone.com/tvgW71
language:
Java (HotSpot 12)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!