首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#7273

求逆序对数 对于一个长度为N的整数序列A,满足i < j 且 A i > A j .的数对(i,j)称为整数序列A的一个逆序 请求出整数序列A的所有逆序对个数…

求逆序对数

对于一个长度为N的整数序列A,满足i < j 且 Ai > Aj.的数对(i,j)称为整数序列A的一个逆序

请求出整数序列A的所有逆序对个数

时间限制:500

内存限制:65536

输入

输入包含多组测试数据,每组测试数据有两行 第一行为整数N(1 <= N <= 20000),当输入0时结束 第二行为N个整数,表示长为N的整数序列

输出

每组数据对应一行,输出逆序对的个数

样例输入

5
1 2 3 4 5
5
5 4 3 2 1
1
1
0

样例输出

0
10
0
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; const int N = 20005; int merge(int a[], int s, int m, int e) {   vector&lt;int&gt; a1;   int m1 = s, m2 = m + 1, c = 0;   while (m1 &lt;= m &amp;&amp; m2 &lt;= e) {     if (a[m1] &gt; a[m2]) {       c += m - m1 + 1;       a1.push_back(a[m2]);       m2++;     } else {       a1.push_back(a[m1]);       m1++;     }   }   while (m1 &lt;= m) {     a1.push_back(a[m1]);     m1++;   }   while (m2 &lt;= e) {     a1.push_back(a[m2]);     m2++;   }   int k = 0;   for (int i = s; i &lt;= e; i++)     a[i] = a1[k++];   return c; } int solve(int a[], int s, int e) {   if (s &gt;= e)     return 0;   int m = (s + e) / 2;   int l = solve(a, s, m);   int r = solve(a, m + 1, e);   int l_r = merge(a, s, m, e);   return l + r + l_r; } int main() {   int n;   int a[N];   while (scanf("%d", &amp;n) &amp;&amp; n != 0) {     for (int i = 0; i &lt; n; i++)       scanf("%d", &amp;a[i]);     int sum = solve(a, 0, n - 1);     cout &lt;&lt; sum &lt;&lt; endl;   }   return 0; }</pre>
这道题暂未补解析。