2013年8月19日

UVa 10810 - Ultra-QuickSort

#include <cstdio>

int num[500000], temp[500000];
long long swap;

void sort(int l, int r) {
  if (r - l <= 1) {
    return;
  }
  int mid = (l + r) / 2;
  sort(l, mid);
  sort(mid, r);
  int i = l, j = mid, k = 0;
  while (i < mid && j < r) {
    if (num[i] > num[j]) {
      temp[k++] = num[j++];
      swap += mid - i;
    } else {
      temp[k++] = num[i++];
    }
  }
  while (i < mid) {
    temp[k++] = num[i++];
  }
  while (j < r) {
    temp[k++] = num[j++];
  }
  for (i = l; i < r; i++) {
    num[i] = temp[i - l];
  }
}

int main() {
  int n;
  while (scanf("%d", &n) && n) {
    for (int i = 0; i < n; i++) {
      scanf("%d", &num[i]);
    }
    swap = 0;
    sort(0, n);
    printf("%lld\n", swap);
  }
  return 0;
}

沒有留言:

張貼留言