数据结构 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

 1 #include <stdio.h>
 2 #include <iostream>
 3 
 4 class A
 5 {
 6 public:
 7     A(int _maxsize)
 8         :ans(0),size(0)
 9     {
10         arr = new int[_maxsize+5];
11     }
12     ~A()
13     {
14         delete arr;
15     }
16     void insert(int n)
17     {
18         int pos = findInsertPos(n);
19         ans += pos;
20         for(i=size;i>pos;i--)
21         {
22             arr[i] = arr[i-1];
23         }
24         arr[pos] = n;
25         size++;
26     }
27     __int64 getAns()
28     {
29         return ans;
30     }
31     void _disAll()
32     {
33         for(i=0;i<size;i++)
34             printf("%d ",arr[i]);
35         printf("
");
36     }
37 private:
38     int findInsertPos(int n)
39     {
40         if(size==0)
41         {
42             return 0;
43         }
44         else if(n <= arr[0])
45         {
46             return 0;
47         }
48         else if(n>arr[size-1])
49         {
50             return size;
51         }
52         else
53         {
54             int l=0,r=size-1,mid=(l+r)/2;
55             for( ; l<r ; mid=(l+r)/2)
56             {
57                 if(arr[mid]<n && n<=arr[mid+1])
58                 {
59                     return mid+1;
60                 }
61                 else if(n>arr[mid])
62                 {
63                     l=mid;
64                 }
65                 else// if(arr[mid]>n)
66                 {
67                     r=mid;
68                 }
69             }
70 //            printf("error! no found
");
71             return 0;
72         }
73     }
74 private:
75     __int64 ans;
76     int *arr;
77     int size;
78     int i,j;
79 };
80 
81 int main()
82 {
83 //    freopen("in.txt","r",stdin);
84     int n,i,buf;
85     scanf("%d",&n);
86     A obj(n);
87     for(i=0;i<n;i++)
88     {
89         scanf("%d",&buf);
90         obj.insert(buf);
91 //        obj._disAll();//tester
92     }
93     printf("%I64d",obj.getAns());
94     
95     
96     return 0;
97 }

解法2

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 __int64 ans=0;
 5 int *arr=NULL,*buf=NULL;
 6 int len=0;
 7 
 8 void init()
 9 {
10     ans=0;
11     int i;
12     scanf("%d",&len);
13     arr = (int *)malloc(sizeof(int)*len);
14     buf = (int *)malloc(sizeof(int)*len);
15     for(i=0;i<len;i++)
16         scanf("%d",arr+i);
17     
18 }
19 void disAll();
20 void mergeSort(int *p, int l, int r)//归并 从大到小 
21 {
22     if(l>=r) return;
23     if(r==l+1)
24     {
25         if(p[l]<p[r])
26         {
27             p[l]^=p[r];
28             p[r]^=p[l];
29             p[l]^=p[r];
30             ans++;//
31         }
32     }
33     else
34     {
35         int m = (l+r)/2;
36         mergeSort(p,l,m);
37         mergeSort(p,m+1,r);
38         
39         int i,j,k;
40         for(i=l;i<=r;i++) 
41             buf[i]=p[i];
42         for(k=l,i=l,j=m+1;k<=r;)
43         {
44             if(i>m)
45                 p[k++] = buf[j++];
46             else if(j>r)
47                 p[k++] = buf[i++];
48             else if(buf[i]>=buf[j])
49                 p[k++] = buf[i++];
50             else// if(buf[j]>buf[i])
51             {
52                 ans+=m+1-i;//
53                 p[k++] = buf[j++];
54             }
55         }
56     }
57 }
58 
59 void deleteAll()
60 {
61     if(arr) free(arr);
62     if(buf) free(buf);
63 }
64 
65 void  disAns()
66 {
67     printf("%I64d",ans);
68 }
69 
70 void _disAll()
71 {
72     for(int i=0;i<len;i++)    
73         printf("%d ",arr[i]);
74     printf("
");
75 }
76 
77 int main()
78 {
79     init();
80     mergeSort(arr,0,len-1);
81     disAns();
82     
83     deleteAll();
84     return 0;
85 }