poj2299Ultra

浏览: 63 发布日期: 2017-07-01 分类: c++

Description

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

题意是求归并排序时,至少要交换几次相邻的数字。
别人都说是求逆序对,规模这么大肯定不能暴力,这里还有个性质,要模拟一下归并排序,在归并排序的合并操作里,对于数列[l, mid] [mid + 1, r]的合并,i 从l开始循环,j从mid + 1开始循环,如果遇到a[i] > a[j] 则出现逆序,可以将a[j]放入辅助数组,同时j++,那么和a[j]逆序的数就有mid-i+1个,因为序列是有序的[i, mid]的所有的数都是大于a[j]的[见]http://www.cnblogs.com/ylfdrib/archive/2010/11/29/1891186.html

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define INF 0x3f3f3f3f
#define MAXN 500005
#define Mod 10001
using namespace std;
long long a[MAXN],b[MAXN],ans;
void copy(long long a[],int l,int r)
{
    for(int i=l;i<=r;++i)
        a[i]=b[i];
}
void merge(long long a[],int l,int mid,int r)
{
    int i=l,j=mid+1;
    int s=l;
    while(i<=mid&&j<=r)
    {
        if(a[i]>1;
        mergesort(a,l,m);
        mergesort(a,m+1,r);
        merge(a,l,m,r);
        copy(a,l,r);
    }
}
int main()
{
    int n;
    while(~scanf("%d",&n)&&n)
    {
        ans=0;
        for(int i=1; i<=n; ++i)
            scanf("%I64d\n",&a[i]);
        mergesort(a,1,n);
        printf("%I64d\n",ans);
    }
    return 0;
}
以上就是poj2299Ultra的全文介绍,希望对您学习和使用c++编程开发有所帮助.
返回顶部