#P5125. [Lydsy1712月赛]小Q的书架
[Lydsy1712月赛]小Q的书架
小 Q 的书架
题目描述
小 Q 有 本编号互不相同的书,正零乱地在地上排成一排。他要将这一排书划分成恰好 个非空连续段,然后按现在的顺序将每段放到一层书架上。
放好后,他要将每层的书分别按编号从小到大排序。每次可以在1单位时间内交换同一层的两本相邻的书。
请计算如何划分及交换,能使总交换次数最少。
输入格式
从标准输入读入。
第一行两个正整数 ,,。
第二行 个互不相同的正整数 ,,表示地面上各本书的编号。
输出格式
向标准输出写出一行一个整数,表示最少的总交换次数。
样例输入
6 3
4 3 6 2 5 1
样例输出
1
样例说明
按 、、 划分,需要交换 次。
原题时间限制20秒,空间限制256 MB。
鸣谢Claris提供
相关
在下列比赛中: