逆序对 POJ2299

逆序对 POJ2299"/>

逆序对 POJ2299

逆序对POJ2299

思路

题干在这：POJ2299
我们采用归并排序的方法，边排序边统计逆序对，输出即可。注意边界条件。
有一个坑就是最后的结果超过int范围，我提交WA，还是看了别人的题解才知道是这里有问题……

ac代码

#include<stdio.h>
#include<iostream>
using namespace std;
int in[500001] = { 0 };
int sort[500001] = { 0 };
long long resort = 0;
void mergesort(int x, int y) {   //[x,y)内的归并排序，并统计逆序对if (y - x <= 1)return;int mid = (x + y) / 2;mergesort(x, mid);mergesort(mid, y);int p = x, q = mid, r = x;while (r != y) {if (q == y || p < mid && in[p] <= in[q]) {sort[r] = in[p];r++;p++;}else {sort[r] = in[q];r++;q++;resort += mid - p;}}for (int i = x; i < y; i++) {in[i] = sort[i];}
}
int main() {while (1) {int n;cin >> n;if (n == 0)return 0;memset(in, 0, sizeof(in));memset(sort, 0, sizeof(sort));for (int i = 1; i <= n; i++) {cin >> in[i];}resort = 0;mergesort(1, n + 1);cout << resort << endl;}
}