A46333. 求逆序对数对于一个长度为N的整数序列A，满足i < j 且 Ai > Aj.的数对(i,j)称为整数序列A的一个逆序请求出整数序列A的所有逆序对个数输入输入包含多组测试数据，每组测试数据有两行 第一行为整数N(1 <= N <= 20000)，当输入0时结束 第二行为N个整数，表示长为N的整数序列输出每组数据对应一行，输出逆序对的个数样例输入51 2 3 4 555 4 3 2 1110样例输出…
填空题
困难
知识点
题目描述
求逆序对数
对于一个长度为N的整数序列A，满足i < j 且 Ai > Aj.的数对(i,j)称为整数序列A的一个逆序
请求出整数序列A的所有逆序对个数
输入
输入包含多组测试数据，每组测试数据有两行 第一行为整数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
参考答案
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <cstring>
using namespace std;
int main()
{
int m;
cin >> m;
while (m != 0)
{
int a[20005] = { 0 };
for (int i = 0; i < m; i++)
{
cin >> a[i];
}
int count = 0;
for (int i = 1; i < m; i++)
{
for (int j = m - 1; j >= i; j--)
{
if (a[j] < a[j - 1])
{
count++;
int t = a[j];
a[j] = a[j - 1];
a[j - 1] = t;
}
}
}
cout << count << endl;
cin >> m;
}
return 0;
}
上一题
下一题