Sort(归并)

Sort

时间限制：1000 ms | 内存限制：65535 KB

难度：4

描述: You want to processe a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. Then how many times it need. For example, 1 2 3 5 4, we only need one operation : swap 5 and 4.

输入

The input consists of T number of test cases.(<0T<1000) Each case consists of two lines: the first line contains a positive integer n (n <= 1000); the next line contains a permutation of the n integers from 1 to n.

输出

For each case, output the minimum times need to sort it in ascending order on a single line.

样例输入

样例输出

0

6
代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int MAXN = ;

int num[MAXN], temp[MAXN];

int ans;

void mg(int l, int m, int r){

    int i = l, j = m + , cur = l;

    while(i <= m && j <= r){

        if(num[i] < num[j]){

            temp[cur++] = num[i++];

        }

        else{

            ans += j - cur;

            temp[cur++] = num[j++];

        }

    }

    for(int i = l; i <= r; i++)

        num[i] = temp[i];

}

void ms(int l, int r){

    int m;

    if(l < r){

        m = (l + r) >> ;

        ms(l, m);

        ms(m + , r);

        mg(l, m, r);

    }

}

int main(){

    int T,n;

    scanf("%d", &T);

    while(T--){

        scanf("%d", &n);

        for(int i = ; i < n; i++){

            scanf("%d", num + i);

        }

        ans = ;

        ms(, n - );

        printf("%d\n", ans);

    }

    return ;

}

巴特西

Sort(归并)

Sort

最新文章

热门文章