fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. long long mergeAndCount(vector<int>& arr, vector<int>& temp, int left, int mid, int right) {
  7.     int i = left;    // 左子數列的起始點
  8.     int j = mid;     // 右子數列的起始點
  9.     int k = left;    // 合併後數列的起始點
  10.     long long inv_count = 0;
  11.  
  12.     // 合併左子數列和右子數列
  13.     while (i <= mid - 1 && j <= right) {
  14.         if (arr[i] <= arr[j]) {
  15.             temp[k++] = arr[i++];
  16.         } else {
  17.             temp[k++] = arr[j++];
  18.             inv_count += (mid - i); // 計算逆序數對
  19.         }
  20.     }
  21.  
  22.     // 複製剩餘的左子數列元素（如果有）
  23.     while (i <= mid - 1) {
  24.         temp[k++] = arr[i++];
  25.     }
  26.  
  27.     // 複製剩餘的右子數列元素（如果有）
  28.     while (j <= right) {
  29.         temp[k++] = arr[j++];
  30.     }
  31.  
  32.     // 複製合併後數列到原數列中
  33.     for (i = left; i <= right; i++) {
  34.         arr[i] = temp[i];
  35.     }
  36.  
  37.     return inv_count;
  38. }
  39.  
  40. long long mergeSortAndCount(vector<int>& arr, vector<int>& temp, int left, int right) {
  41.     long long inv_count = 0;
  42.     if (right > left) {
  43.         int mid = (left + right) / 2;
  44.  
  45.         inv_count += mergeSortAndCount(arr, temp, left, mid);
  46.         inv_count += mergeSortAndCount(arr, temp, mid + 1, right);
  47.         inv_count += mergeAndCount(arr, temp, left, mid + 1, right);
  48.     }
  49.     return inv_count;
  50. }
  51.  
  52. long long calculateDiscomfort(vector<int>& arr) {
  53.     int n = arr.size();
  54.     vector<int> temp(n);
  55.     long long inv_count = mergeSortAndCount(arr, temp, 0, n - 1);
  56.  
  57.     long long discomfort = 0;
  58.     for (int i = 0; i < n; i++) {
  59.         for (int j = i + 1; j < n; j++) {
  60.             if (arr[i] > arr[j]) {
  61.                 discomfort += arr[i] + arr[j];
  62.             }
  63.         }
  64.     }
  65.  
  66.     return discomfort;
  67. }
  68.  
  69. int main() {
  70.     int n;
  71.     cin >> n;
  72.     vector<int> arr(n);
  73.     for (int i = 0; i < n; i++) {
  74.         cin >> arr[i];
  75.     }
  76.  
  77.     cout << calculateDiscomfort(arr) << endl;
  78.  
  79.     return 0;
  80. }
  81.  
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
5
5 4 2 1 3
stdout
copy 
0
https://ideone.com/9JTkvq
language:
C++14 (gcc 8.3)
created:
5 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!