塔子哥是一个学生,他最近学习的时候遇到了一个题目,题目给定了一个长度为 n 的排列吗,题目要求将这个排列的前 k 个数排列成一个长度为 k 的排列,但是题目规定只能进行相邻两个数的交换操作,题目问最少需要多少次上述操作才能满足题目要求?
塔子哥思考了很久还是不会,他现在想请教你,想让你帮忙解决一下这个问题。
长度为 n 的排列指 1 到 n 中每个数都恰好出现 1 次。例如 [2,3,1] 是排列, [2,3,4] 则不是排列。
第一行输入两个正整数 n 和 k 。
第二行输入 n 个正整数 ai ,代表塔子哥拿到的排列。
1≤k≤n≤200000
1≤ai≤n
一个整数,代表最小的操作次数。
输入
5 3
2 4 1 3 5
输出
2
样例解释
第一次交换 4 和 1 ,数组变成 [2,1,4,3,5] 。
第二次交换 4 和 3 ,数组变成 [2,1,3,4,5] 。
此时前 3 个数构成排列,满足条件。
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.