大意:将无序的序列通过两两交换最少需要几次才能有序。
思路:可以证明即数列的逆序对数,于是归并排序求解。
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
const int MAXN = 500010;
int n;
typedef long long LL;
LL A[MAXN], T[MAXN];
void merge_sort(int x, int y, LL &ans)
{
if(y-x > 1)
{
int m = x + (y-x)/2;
int p = x, q = m, i = x;
merge_sort(x, m, ans);
merge_sort(m, y, ans);......
阅读全文