| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1364
逆序对计数
Time Limit: 1000ms
Memory Limit: 65536kb Description
在一个包含n个非负整数的数列{Ak}中，对任意满足i<j的下标i、j，称满足条件A[i]>A[j]的数对(A[i], A[j])为逆序对。例如数列（3，1，4，5，2）的所有逆序对为(3,1), (3,2), (4,2), (5,2)，共4个。本题中要解决的问题是，针对给定的数列，求出数列中所包含的逆序对个数。
Input
输入格式：每一个测试样例包含两行输入，第一行是数列的个数n（2 <= n <= 500），第二行由n个整数组成的数列（非负，且小于1000），数与数间以空格隔开。输入以n等于-1作为结束标志。
Output
每一个测试数列仅有一行输出，且只包含该测试数列的逆序对个数。
Sample Input
3 1 6 8 5 2 6 3 1 9 -1 Sample Output
0 4 |