简答题 偏难
#7120

求逆序对数 对于一个长度为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;algorithm&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;map&gt; #include &lt;string&gt; using namespace std; int main() {   int m;   cin &gt;&gt; m;   while (m != 0) {     int a[20005] = {0};     for (int i = 0; i &lt; m; i++) {       cin &gt;&gt; a[i];     }     int count = 0;     for (int i = 1; i &lt; m; i++) {       for (int j = m - 1; j &gt;= i; j--) {         if (a[j] &lt; a[j - 1]) {           count++;           int t = a[j];           a[j] = a[j - 1];           a[j - 1] = t;         }       }     }     cout &lt;&lt; count &lt;&lt; endl;     cin &gt;&gt; m;   }   return 0; }</pre>
这道题暂未补解析。