Preparing NOJ

Sorting Problem I

1000ms 16384K

Description:

openxxx喜欢一切有序的事物,现在有一串数字,openxxx希望以最小的代价对这串数字从小到大进行排序(实现非递减序)。

openxxx只会交换任意两个相邻的数字,每做一次交换,就要消耗openxxx一格的体力值,当然openxxx希望消耗的体力值越少越好,你能计算出openxxx至少要消耗多少格体力值吗?

Input:

多组测试数据,每组数据第一行包含一个正整数N(1<=N<=500)表示这串数字的个数,第二行包含N个正整数x1 x2 x3 …… xN(1<=xi<=N,1<=i<=N)用来描述这串原始数字序列,任意两个相邻数字之间用一个空格隔开。 


Output:

每组测试数据对应一行输出,仅包含一个整数p,表示最少需要消耗的体力值数。


Sample Input:

2
1 2
3
3 1 2
2
1 1

Sample Output:

0
2
0

Note:

本题由旧版NOJ导入,来源:2012南京邮电大学第四届大学生程序设计大赛(预赛)

Info

NOJ

Provider NOJ

Code NOJ1870

Tags

Submitted 1

Passed 1

AC Rate 100%

Date 04/20/2019 10:03:10

Related

Nothing Yet