【题解】P1908 -归并排序求逆序对和
权御天下
2018-10-22 21:26:32
#### 在解题之前，先让我们来看一看本题会用到而萌新可能不懂的几个事项：
本题大意：对于给定的无序数组，求出经过最少多少次相邻元素的交换之后，可以使数组从小到大有序
对于逆序对的解释：两个数（a, b）的排列，若满足a > b，则称之为一个逆序对
归并排序的思想：先把每个数看成一段，然后两两合并成一个较大的有序数组，再把较大的两两合并，直到最后成为一个有序数组
归并排序复杂度：$ O(nlogn) $
#### 接下来就是我们解题的步骤了:
根据排序算法，我们知道如果相邻的两个元素满足前一个大于后一个便会交换一次，由于题目要求排序后是单调递增，所以我们可以将这道题看做求原数组逆序对的数量
举一个归并排序的例子：
假设初始数组为4 2 1 3
先把每一个数单独分成一组，即(4) (2) (1) (3)
接着两两合并，即(2 4) (1 3)
最后合成一个有序的数组，即(1 2 3 4)
不难发现，在排序过程中，若某个数向前移动了N位，则必定存在N个逆序数,如上面例子中，数字1由原先的第三位移到了第一位，前移了两位，则存在(2 1)和(4 1)两个逆序
而根据题意，我们只需要在归并排序的过程中把这个数记下来即可
接下来上一下代码
顺便安利一波自己的io模板：自测结果：不加io优化跑了1108ms，加了优化后仅跑了797ms（看近期大多数的提交都是1200ms+ ，快一点的也都是1000ms+，797ms应该算是比较快的）
io模板详解链接：https://twi.blog.luogu.org/duliu-io
```cpp
#include<cstdio>
using namespace std;
#define ll long long
namespace io { //io模板详见个人博客
#define gc() (iS == iT ? (iT = (iS = ibuff) + fread(ibuff, 1, SIZ, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
const int SIZ = 1 << 21 | 1;
char *iS, *iT, ibuff[SIZ], obuff[SIZ], *oS = obuff, *oT = oS + SIZ - 1, fu[110], c;
int fr;
inline void out() {
fwrite(obuff, 1, oS - obuff, stdout);
oS = obuff;
}
template<class Type>
inline void read(Type &x) {
x = 0;
Type y = 1;
for (c = gc(); (c > '9' || c < '0') && c != '-'; c = gc());
c == '-' ? y = -1 : x = (c & 15);
for (c = gc(); c >= '0' && c <= '9'; c = gc())
x = x * 10 + (c & 15);
x *= y;
}
template<class Type>
inline void print(Type x, char text = '\n') {
if (x < 0)
*oS++ = '-', x *= -1;
if (x == 0)
*oS++ = '0';
while (x)
fu[++fr] = x % 10 + '0', x /= 10;
while (fr)
*oS++ = fu[fr--];
*oS++ = text;
out();
}
}
using namespace io; //以上为玄(du)学(liu)优(ka)化(chang)
ll ans[500010], mem[500010], anss;
int n;
void merge(int lo, int mid, int hi) {
int i = lo, e = mid + 1, k = lo;
while (i <= mid && e <= hi) {
if (ans[i] <= ans[e])
mem[k++] = ans[i++];
else
anss += e - k, mem[k++] = ans[e++]; //求逆序对和
}
while (i <= mid)
mem[k++] = ans[i++];
while (e <= hi)
mem[k++] = ans[e++];
for (i = lo; i <= hi; ++i)
ans[i] = mem[i];
}
void merge_sort(int x, int y) {
if (x < y) {
int mid = (x + y) / 2;
merge_sort(x, mid);
merge_sort(mid + 1, y);
merge(x, mid, y);
}
}
int main() {
read(n);
for (register int i = 0; i < n; ++i)
read(ans[i]);
merge_sort(0, n - 1);
print(anss);
return 0;
}
```
我们的信条就是，用最短的码长，写出跑的最快的代码（不算io优化本人代码码长仅为0.8kb，在题解中也算是比较短的代码了）
码风诡异请不要在意QAQ
这道题就到这里，让我们下一道题见（发出咕咕咕的声音）