求解逆序数

逆序数求解，同于POJ2299题。

常规做法是使用O(N^2)的两重循环，逐个遍历

for i = (0, N)

for j = (i+1, N)

if(a[i] > a[j])

count++;

return count;

推荐的做法是使用类似于归并排序的方法，可以再O(NlogN)内算出。

输入格式：

5（个数） 9
1
0
5
4
3（个数）
1 2
3
0（个数为0表示结束）

1  #include<cstdio>
 2  #include<iostream>
 3  #include<fstream>
 4  using namespace std;
 5 
 6  #define MAX 1000000000
 7  #define N 500005
 8  
 9  long long a[N],b[N],c[N];
10  
11  inline long long Merge(int p,int q,int r)
12  {
13      long long cnt = 0 ;
14      for(int i=p;i<=q;i++)
15          b[i] = a[i];
16      for(int i=q+1;i<=r;i++)
17          c[i] = a[i];
18      b[q+1] = c[r+1] = MAX;
19      int bb = p, cc = q+1;
20      for(int i=p;i<=r;i++)
21      {
22          if(b[bb] <= c[cc])   //求逆序 需要写成<=
23          {
24              a[i] = b[bb++];
25          }
26          else
27          {
28              a[i] = c[cc++];
29              cnt += (q+1 - bb);        //主要是该步，只有b[bb] > c[cc],那么一定有 bb到q+1之间的数 大于 c[cc]。
30          }
31      }
32      return cnt;
33  }
34  
35  long long MergeSort(int p,int r)
36  {
37      long long cnt = 0;
38      if(p==r) return 0;
39      int q = (p+r)/2;
40      cnt += MergeSort(p,q);
41      cnt += MergeSort(q+1,r);
42      cnt += Merge(p,q,r);
43      return cnt;
44  }
45  
46  int main(int argc, char **argv)
47  {
48      ifstream fin(argv[1]);
49      int n;
50      while(1)
51      {
52          fin >> n;
53          if(!n)
54              break;
55          for(int i=0;i<n;i++)
56              fin >> a[i];
57          printf("%I64d\n",MergeSort(0,n-1));
58      }
59 
60      system("pause");
61      return 0;
62  }

原文链接: https://www.cnblogs.com/dandingyy/archive/2012/09/16/2688053.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍