http://poj.org/problem?id=2299
题意：
给定一组有n个数的序列，每次交换相邻两个元素，至少多少次才能使序列为非递减序列。
输入包括多组数据，每组数据第一行为一个整数n（n=0时输入结束），接下来n行有个整数，每组数据输出一行，表示最少交换次数
思路：
实际上就是求这个序列的逆序数问题，采用归并排序，对子问题进行和并的过程中同时计算逆序数。
对长度为n的序列进行归并排序：若n为1，算法终止；否则，将这个序列分成左右两个子序列，对每个序列分别进行归并排序，然后将排好序的子序列进行合并。
在合并过程中，维护左右两个序列的下标，如果当前左边的值大于右边的值，则左边剩下的数都大于右边的这个数，此时应对逆序数更新，右边的下标向后移动；否则，左边的下标向后移动。
PS:
strcpy只能复制字符串；
memcpy可以复制任意内容（字符数组，整型，结构体，类等）
在头文件#include<string.h>或#include<cstring>中
原型：
void *memcpy(void *destin, void *source, unsigned n);
destin-：用于存储复制内容的目标数组
source-：指向要复制的数据源
n-：要被复制的字节数
代码：
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<string> #include<iomanip> #include<algorithm> #include<string.h> #include<queue> using namespace std; const int maxn=5e5+10; const int inf=2147483647; typedef long long ll; int a[maxn],l[maxn],r[maxn]; ll sum=0; void mergesort(int s,int e) { if(s==e) return ; int mid=(s+e)/2; mergesort(s,mid); mergesort(mid+1,e); memcpy(l+1,a+s,(mid-s+1)*4); memcpy(r+1,a+mid+1,(e-mid)*4); l[mid-s+2]=r[e-mid+1]=inf; int left_num=mid-s+1; int left_i=1,right_i=1; for(int i=s; i<=e; i++) { if(l[left_i]>r[right_i]) { a[i]=r[right_i++]; sum+=left_num; } else { a[i]=l[left_i++]; left_num--; } } } int main() { int n; while(cin>>n&&n) { sum=0; for(int i=1; i<=n; i++) cin>>a[i]; mergesort(1,n); cout<<sum<<endl; } system("pause"); return 0; }
POJ-2299-Ultra-QuickSort(分治+memcpy用法)
原文：https://www.cnblogs.com/sweetlittlebaby/p/14322986.html