poj 2299 Ultra-QuickSort（树状数组+离散化的题目）据说是简单题，不过还是觉得好难。。。-白红宇

poj 2299 Ultra-QuickSort（树状数组+离散化的题目）据说是简单题，不过还是觉得好难。。。

阅读量：4035 次

发布时间：2019-05-24

本文共 2301 字，大约阅读时间需要 7 分钟。

1、

2、题目大意：

一个序列有n个数字，他们是无序的，现在要将这些数字交换顺序，使得他们是从小到大排列的，输出最少交换几次，3、思路分析

如果数字个数很小的话，实际上是可以用冒泡排序的，冒泡交换的步数实际上就是所求，但是数据很大，所以不能这么做，看网上解题报告用树状数组解决，作为第一个树状数组的题目，真心觉得好难，还得继续看，

还有一个问题就是除了n非常大不能用冒泡做，还有就是这n个数字也是非常大的，所以要用到离散化

4、题目

Ultra-QuickSort

Time Limit: 7000MS		Memory Limit: 65536K
Total Submissions: 37365		Accepted: 13438

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

59105431230

Sample Output

Source

5、AC代码：

#include
   
    #include
    
     #include
     
      using namespace std;#define N 500005int b[N],n,c[N];struct node{    int id;    int x;} a[N];int cmp(node a,node b){    return a.x
      
       0)    {        tmp+=c[i];        i-=i&(-i);    }    return tmp;}int main(){    while(scanf("%d",&n)!=EOF)    {        if(n==0)            break;        memset(b,0,sizeof(b));        memset(c,0,sizeof(c));        for(int i=1; i<=n; i++)        {            scanf("%d",&a[i].x);            a[i].id=i;        }        sort(a+1,a+n+1,cmp);        //离散化        a[0].x=-1;        for(int i=1; i<=n; i++)        {            if(a[i].x!=a[i-1].x)                b[a[i].id]=i;            else                b[a[i].id]=b[a[i-1].id];        }        long long ans=0;        for(int i=1; i<=n; i++)        {            //每次更新后判断左边比当前数大的数的个数            update(b[i],1);            ans+=sum(n)-sum(b[i]);        }        printf("%lld\n",ans);    }    return 0;}

转载地址：http://owcdi.baihongyu.com/

你可能感兴趣的文章