UVa 299

Tree's a Crowd

from Volume 1. Elementary Problem Solving :: Sorting/Searching

Description

火车可以通过 swapping 装置， 调换相邻两节车厢的位置。按顺序给出每节车厢的编号， 请调换火车的车厢， 使得车厢的编号升序。请求出最少要用到几次 swapping 装置。

Solution

题目实则求解一段序列中的逆序对数。方法有很多， 况且这题 n 极小， 只要能求出逆序对数， 几乎都可以过。