4173: 逆序对(inversion)
Memory Limit:128 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:68
Solved:45
Description
【问题描述】
设A[1..N]是一个包含N个数的数组.如果在i小于j的情况下,有A[i]>A[j],则(i,j)就称为A中的一个逆序对。
【输入文件】
第一行为一个正整数N,接下来一行N个正整数表示A[1]..A[N]。
【输出文件】
逆序对数.
【输入样例】
5
2 3 8 6 1
【输出样例】
5
【数据规模】
对于30%的数据,N<=100;
对于100%的数据,N<=100000 ; -10^9 < a[i] < 10^9;