思路：贪心

解决这个问题的关键在于如何选择交换哪两个数，我们可以观察到，为了最小化交换操作的次数，我们应该优先将大于$k$的数移出前$k$个数，同时将1到$k$的数移入前$k$个数。

由于本题只能交换相邻两个数字，因此，我们可以首先找出前$k$个数中大于$k$的数的位置，然后找出后$n-k$个数中1到$k$的数的位置，然后计算这两个位置的差值的绝对值，这个差值就是需要的最少交换次数。

具体实现我们可以使用两个数组去分别记录$[1,k]$的下标和$[k+1,n]$的下标，然后根据上述计算规则去计算

代码

C++

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
#define x first
#define y second
typedef long long ll;
const int N=2E5+10;
int n,w[N],k;
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>w[i];
    vector<int>pos1,pos2;
    for(int i=0;i<k;i++)
    {
        if(w[i]>k)pos1.push_back(i);
    }
    for(int i=k;i<n;i++)
    {
        if(w[i]>=1&&w[i]<=k)pos2.push_back(i);
    }
    int m=pos2.size();
    ll res=0;
    for(int i=0;i<m;i++)
    {
        res+=pos2[i]-pos1[i];
    }
    cout<<res<<endl;
    return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] w = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = scanner.nextInt();
        }
        List<Integer> pos1 = new ArrayList<>();
        List<Integer> pos2 = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            if (w[i] > k) {
                pos1.add(i);
            }
        }
        for (int i = k; i < n; i++) {
            if (w[i] >= 1 && w[i] <= k) {
                pos2.add(i);
            }
        }
        int m = pos2.size();
        long res = 0;
        for (int i = 0; i < m; i++) {
            res += pos2.get(i) - pos1.get(i);
        }
        System.out.println(res);
    }
}

Python

n, k = map(int, input().split())
w = list(map(int, input().split()))

pos1 = []
pos2 = []

for i in range(k):
    if w[i] > k:
        pos1.append(i)

for i in range(k, n):
    if 1 <= w[i] <= k:
        pos2.append(i)

m = len(pos2)
res = 0

for i in range(m):
    res += pos2[i] - pos1[i]

print(res)

题目内容

小红是一个学生，他最近学习的时候遇到了一个题目，题目给定了一个长度为 $n$ 的排列吗，题目要求将这个排列的前 $k$ 个数排列成一个长度为 $k$ 的排列，但是题目规定只能进行相邻两个数的交换操作，题目问最少需要多少次上述操作才能满足题目要求？

小红思考了很久还是不会，他现在想请教你，想让你帮忙解决一下这个问题。

长度为 $n$ 的排列指 $1$ 到 $n$ 中每个数都恰好出现 $1$ 次。例如 $[2,3,1]$ 是排列， $[2,3,4]$ 则不是排列。

输入描述

第一行输入两个正整数 $n$ 和 $k$ 。

第二行输入 $n$ 个正整数 $a_i$ ，代表小红拿到的排列。

$1\le k\le n\le 200000$

$1\le a_i\le n$

输出描述

一个整数，代表最小的操作次数。

样例

输入

5 3
2 4 1 3 5

输出

2

样例解释

第一次交换 $4$ 和 $1$ ，数组变成 $[2,1,4,3,5]$ 。

第二次交换 $4$ 和 $3$ ，数组变成 $[2,1,3,4,5]$ 。

此时前 $3$ 个数构成排列，满足条件。