B - Merge Sort

問題

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_B

問題文

マージソートの疑似コード:

merge(A, left, mid, right)
  n1 = mid - left;
  n2 = right - mid;
  L[0...n1], R[0...n2] を生成
  for i = 0 to n1-1
    L[i] = A[left + i]
  for i = 0 to n2-1
    R[i] = A[mid + i]
  L[n1] = INFTY
  R[n2] = INFTY
  i = 0
  j = 0
  for k = left to right-1
    if L[i] <= R[j]
      A[k] = L[i]
      i = i + 1
    else
      A[k] = R[j]
      j = j + 1

mergeSort(A, left, right)
  if left+1 < right
    mid = (left + right)/2;
    mergeSort(A, left, mid)
    mergeSort(A, mid, right)
    merge(A, left, mid, right)

$n$ 要素の数列 $S$ をマージソートで昇順に並び変えて、 merge における比較回数の総数を報告して。

制約

• $n \le 500,000$
• $0 \le S_i \le 10^9$

サンプル

I/O 1

10
8 5 9 2 6 3 7 1 10 4

10
8 5 9 2 6 3 7 1 10 4

考察

いわれたとおりにやる

コード

https://onlinejudge.u-aizu.ac.jp/status/users/a01sa01to/submissions/1/ALDS1_5_B/judge/6771408/C++17

void merge(vector<int>& a, int l, int mid, int r, int& cnt) {
  int n1 = mid - l, n2 = r - mid;
  vector<int> left(n1 + 1), right(n2 + 1);
  rep(i, n1) left[i] = a[l + i];
  rep(i, n2) right[i] = a[mid + i];
  left[n1] = 1e9, right[n2] = 1e9;
  int i = 0, j = 0;
  for (int k = l; k < r; k++) {
    cnt++;
    if (left[i] <= right[j]) {
      a[k] = left[i];
      i++;
    }
    else {
      a[k] = right[j];
      j++;
    }
  }
}

void MergeSort(vector<int>& a, int& cnt, int l, int r) {
  if (l + 1 < r) {
    int mid = (l + r) / 2;
    MergeSort(a, cnt, l, mid);
    MergeSort(a, cnt, mid, r);
    merge(a, l, mid, r, cnt);
  }
}

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  int cnt = 0;
  MergeSort(a, cnt, 0, n);
  rep(i, n) cout << a[i] << (i == n - 1 ? "\n" : " ");
  cout << cnt << endl;
  return 0;
}