数据结构 nxd(顺序对)

问题描述

　　给定 n 个数 a1,a2,...,an，求满足条件的(i,j)数量： i<j 且 a[i]<a[j]

★数据输入
输入第一行为一个正整数 n。
第二行为 n 个数，第 i 个代表 ai。
对于 90%的数据， 1<=n<=6666;
对于 100%的数据， 1<=n<=100086， 0<=ai<=1000,000,000;

★数据输出
输出满足条件的（i, j）的数量。

输入示例	输出示例
5 9 1 5 2 2	3

输入示例	输出示例
7 4 3 1 5 5 5 2	10

解题思路

　　解法1：

　　　　插入排序，二分查找

　　　　c++可用vector + lower_bound实现

　　　　注意 100086^2 = 100亿+，结果应用__int64 (long long int) 存

　　解法2：

　　　　手写归并排序，从大到小排列，统计数据左移次数

code

解法1

 #include <stdio.h>

 #include <iostream>

 class A

 {

 public:

     A(int _maxsize)

         :ans(),size()

     {

         arr = new int[_maxsize+];

     }

     ~A()

     {

         delete arr;

     }

     void insert(int n)

     {

         int pos = findInsertPos(n);

         ans += pos;

         for(i=size;i>pos;i--)

         {

             arr[i] = arr[i-];

         }

         arr[pos] = n;

         size++;

     }

     __int64 getAns()

     {

         return ans;

     }

     void _disAll()

     {

         for(i=;i<size;i++)

             printf("%d ",arr[i]);

         printf("\n");

     }

 private:

     int findInsertPos(int n)

     {

         if(size==)

         {

             return ;

         }

         else if(n <= arr[])

         {

             return ;

         }

         else if(n>arr[size-])

         {

             return size;

         }

         else

         {

             int l=,r=size-,mid=(l+r)/;

             for( ; l<r ; mid=(l+r)/)

             {

                 if(arr[mid]<n && n<=arr[mid+])

                 {

                     return mid+;

                 }

                 else if(n>arr[mid])

                 {

                     l=mid;

                 }

                 else// if(arr[mid]>n)

                 {

                     r=mid;

                 }

             }

 //            printf("error! no found\n");

             return ;

         }

     }

 private:

     __int64 ans;

     int *arr;

     int size;

     int i,j;

 };

 int main()

 {

 //    freopen("in.txt","r",stdin);

     int n,i,buf;

     scanf("%d",&n);

     A obj(n);

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

     {

         scanf("%d",&buf);

         obj.insert(buf);

 //        obj._disAll();//tester

     }

     printf("%I64d",obj.getAns());

     return ;

 }

解法2

 #include <stdio.h>

 #include <stdlib.h>

 __int64 ans=;

 int *arr=NULL,*buf=NULL;

 int len=;

 void init()

 {

     ans=;

     int i;

     scanf("%d",&len);

     arr = (int *)malloc(sizeof(int)*len);

     buf = (int *)malloc(sizeof(int)*len);

     for(i=;i<len;i++)

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

 }

 void disAll();

 void mergeSort(int *p, int l, int r)//归并 从大到小

 {

     if(l>=r) return;

     if(r==l+)

     {

         if(p[l]<p[r])

         {

             p[l]^=p[r];

             p[r]^=p[l];

             p[l]^=p[r];

             ans++;//

         }

     }

     else

     {

         int m = (l+r)/;

         mergeSort(p,l,m);

         mergeSort(p,m+,r);

         int i,j,k;

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

             buf[i]=p[i];

         for(k=l,i=l,j=m+;k<=r;)

         {

             if(i>m)

                 p[k++] = buf[j++];

             else if(j>r)

                 p[k++] = buf[i++];

             else if(buf[i]>=buf[j])

                 p[k++] = buf[i++];

             else// if(buf[j]>buf[i])

             {

                 ans+=m+-i;//

                 p[k++] = buf[j++];

             }

         }

     }

 }

 void deleteAll()

 {

     if(arr) free(arr);

     if(buf) free(buf);

 }

 void  disAns()

 {

     printf("%I64d",ans);

 }

 void _disAll()

 {

     for(int i=;i<len;i++)

         printf("%d ",arr[i]);

     printf("\n");

 }

 int main()

 {

     init();

     mergeSort(arr,,len-);

     disAns();

     deleteAll();

     return ;

 }

巴特西

数据结构 nxd(顺序对)

最新文章

热门文章