rqnoj 173 Fish学数学 求逆序数,并归排序的应用
题目是中文的。。其实就是求一个序列的逆序对数,裸题。
用分治的思想来做,并归排序稍微修改下就可以了。
代码:
/* * Author: illuz <iilluzen@gmail.com> * Blog: http://blog.csdn.net/hcbbt * File: rqnoj173.cpp * Lauguage: C/C++ * Create Date: 2013-08-30 09:45:28 * Descripton: rqnoj 1173, partitation */ #include <cstdio> #define rep(i, n) for (int i = 0; i < (n); i++) #define repu(i, a, b) for (int i = (a); i < (b); i++) const int MAXN = 1000100; int n, cnt, a[MAXN], t[MAXN]; void merge(int l, int r) { if (r - l <= 1) return; int m = l + (r - l) / 2; merge(l, m); merge(m, r); int p = l, q = m, i = l; while (p < m || q < r) if (q >= r || (p < m && a[p] <= a[q])) t[i++] = a[p++]; else t[i++] = a[q++], cnt += m - p; repu(i, l, r) a[i] = t[i]; } int main() { scanf("%d", &n); rep(i, n) scanf("%d", &a[i]); cnt = 0; merge(0, n); printf("%d\n", cnt); return 0; }
补充:软件开发 , C++ ,