欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

再见逆序数

程序员文章站 2022-07-03 10:40:52
...

poj-2299-Ultra-QuickSort

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence
9 1 0 5 4 ,

Ultra-QuickSort produces the output
0 1 4 5 9 .

Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
Input
The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 – the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.
Output
For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.
Sample Input
5
9
1
0
5
4
3
1
2
3
0
Sample Output
6
0

大意:给出长度为n的序列,每次只能交换相邻的两个元素,问至少要交换几次才使得该序列为递增序列。
思路:样例少的话直接冒泡统计下交换次数就行了,但这个题就不行了,可以换个方向考虑,逆序数也是交换两个数的位置并排序,可以想到统计下逆序数的个数就行了。

#include<stdio.h>
typedef long long ll;
int a[500010],ans[500010];
int n,i,j,k;

ll solve(int l,int r)
{
    int mid = (l + r) >> 1;
    if(l == r)
        return 0;
    ll num = 0;
    num += solve(l , mid);
    num += solve(mid + 1, r);
    for(i = l, j = mid + 1, k = 0; i <= mid || j <=r; k++)
    {
        if(i > mid) ans[k] = a[j++];
        else if(j > r) ans[k] = a[i++];
        else if(a[i] <= a[j]) ans[k] = a[i++];
        else{

            ans[k] = a[j++];
            num += mid - i + 1;
        }
    }
    for(i = 0; i <= r-l; i++)
        a[i+l] = ans[i];
    return num;
}

int main()
{
    while(scanf("%d",&n)!=EOF && n)
    {
        for(i = 0; i < n; i++)
            scanf("%d",&a[i]);
        printf("%lld\n",solve(0,n-1));
    }
    return 0;
 }