求逆序对数
成绩 | 100 | 开启时间 | 2016年05月24日 星期二 21:25 |
折扣 | 0.8 | 折扣时间 | 2016年05月24日 星期二 21:25 |
允许迟交 | 是 | 关闭时间 | 2016年05月24日 星期二 21:25 |
输入文件 | reverse.in | 输出文件 | reverse.out |
【题目描述】求逆序对数(reverse. cpp/c/pas)
“装满了鹅卵石的瓶子是满的吗?”墨老师曾经这样问过他的学生。“不是,因为还可以放入小石子、再放入细砂、最后再倒入水。”学生们回答。“那么从中可以得到什么启示呢?”墨老师又问,“启示我们时间总是可以挤出来的!”一个聪明的学生抢答。“你说得对!”墨老师微笑道,“但我还要告诉你们另一个重要经验,那就是:如果你不先将大的鹅卵石放进瓶子里去,你也许以后永远没机会再把它们放进去了。”
但这世上的很多人,做事却经常分不清事情的轻重缓急。我们可爱的典狱长大人就犯了这个错误,当他看到身高参差不齐的狱警们排成一列时,眉毛拧成了一个结,他最想知道的就是,到底有多少个狱警逆序排队了。这可以抽象为求逆序对的个数问题:即对于一个包含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个。
【输入文件】
输入文件reverse.in包括两行,第一行是一个整数n(1≤n≤1000),表示狱警人数。第二行包含n个整数,用空格分隔,即每个狱警的身高,狱警身高均在int范围内。
【输出文件】
输出文件reverse.out包括一行,这一行只包含一个整数,即逆序对的个数。
【样例输入】
5
3 1 4 5 2
【样例输出】
4