求逆序对数
成绩 | 100 | 开启时间 | 2020年06月18日 星期四 10:45 |
折扣 | 0.8 | 折扣时间 | 2020年06月18日 星期四 10:45 |
允许迟交 | 是 | 关闭时间 | 2020年06月18日 星期四 10:45 |
输入文件 | reverse.in | 输出文件 | reverse.out |
【题目描述】求逆序对数(reverse)
对于一个包含n个非负整数的数组A[1,…,n],如果有i< j,且A[ i ]>A[ j ],则称(A[i],A[j] )为数组A中的一个逆序对。
例如,数组(3,1,4,5,2)的逆序对有(3,1),(3,2),(4,2),(5,2)共4个。
【输入格式】
输入包括两行,第一行是一个整数n(1≤n≤1 000),表示数的个数。第二行包含n个整数,用空格分隔,即每个数的值,其范围均在int范围内。
【输出格式】
输出包括一行,这一行只包含一个整数,即逆序对的个数。
【输入样例】
5
3 1 4 5 2
【输出样例】
4