洛谷 SP9722 CODESPTB - Insertion Sort
题目描述
Insertion Sort is a classical sorting technique. One variant of insertion sort works as follows when sorting an array a[1..N] in non-descending order:
for i <- 2 to N
j <- i
while j > 1 and a[j] < a[j - 1]
swap a[j] and a[j - 1]
j <- j - 1
The pseudocode is simple to follow. In the ith step, element a[i] is inserted in the sorted sequence a[1..i - 1]. This is done by moving a[i] backward by swapping it with the previous element until it ends up in it's right position.
As you probably already know, the algorithm can be really slow. To study this more, you want to find out the number of times the swap operation is performed when sorting an array.
输入格式
The first line contains the number of test cases T. T test cases follow. The first line for each case contains N, the number of elements to be sorted. The next line contains N integers a[1],a[2]...,a[N].
输出格式
Output T lines, containing the required answer for each test case.
题意翻译
题目大意：
给定一个长度为n的序列，求使其交换至有序（从小到大）的最少交换次数（逆序对）
输入
本题有多组数据
输入一个正整数T，表示有T组数据
对于每组数据
一个正整数n
n个正整数表示这个序列
输出
换行输出每组序列的最小交换次数
输入输出样例
输入 #1复制
输出 #1复制
题解
一道求逆序对的题目。
求逆序对是一个问题，对于这个问题，一般来讲有两种求解方法。详见本蒟蒻博客：
最后在放一波AC代码：
#include<cstdio>
using namespace std;
const int maxn=1e5+1;
int a[maxn],b[maxn],n,ans;
void merge_sort(int l,int r)
{
if(l==r)
return;
int mid=(l+r)>>1;
merge_sort(l,mid);
merge_sort(mid+1,r);
int i=l,j=mid+1,k=l;
while(i<=mid && j<=r)
{
if(a[i]<=a[j])
b[k++]=a[i++];
else
{
b[k++]=a[j++];
ans+=mid-i+1;
}
}
while(i<=mid)
b[k++]=a[i++];
while(j<=r)
b[k++]=a[j++];
for(int p=l;p<=r;p++)
a[p]=b[p],b[p]=0;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
merge_sort(1,n);
printf("%d
",ans);
}
return 0;
}