← 返回题目

题库练习求逆序对数

← 上一题下一题 →

A71272 | $求逆序对数$

来源编程题

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

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

输入格式

输入包含多组测试数据，每组测试数据有两行。 第一行为整数 N(1 \le N \le 20000)，当输入 0 时结束。 第二行为 N 个整数，表示长为 N 的整数序列。（这 N 个数在 [-10^9, 10^9] 的范围内）

输出格式

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

输入输出样例

输入 #1

输出 #1

0
10
0

C++ 编辑器

输入

输出