[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
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.2ms with 1 query(s).