思路：模拟

用手中的数与数组中的数交换，手中的数一定是越来越小的。同时要让数组中的数单调不减，首先就要让最后一个数最大，而如果最后一个数不是最大，唯一改变它的方法就是与手中的数字进行交换。于是手中的数就变为了最后一个数。对于第$n-1,n-2,...$个数同理。

于是从最后一个数开始判断，如果比手中数小，那么就进行交换，同时与前面的数比较，如果逆序，则记录该逆序对。

交换后，与前后两个数进行比较，检查能否删除记录过的逆序对。如果最后没有记录中的逆序对，则说明可以实现，否则不能。

代码

C++

#include <iostream>
#include <vector>
#include <set>

using namespace std;

// 函数检查数组是否已经排序
bool is_sorted(const vector<int>& array, set<int>& unsorted_indices) {
    for (size_t i = 1; i < array.size(); ++i) {
        if (array[i] < array[i - 1]) {
            unsorted_indices.insert(i);
        }
    }
    return unsorted_indices.empty();
}

// 更新集合 unsorted_indices
void update_indices(const vector<int>& array, set<int>& unsorted_indices, int x, int y) {
    if (array[y] < array[x]) {
        unsorted_indices.insert(y);
    } else {
        unsorted_indices.erase(y);
    }
}

// 计算使数组有序所需的最小操作次数
int min_operations_to_sort(vector<int> array, int x) {
    set<int> unsorted_indices;

    // 检查初始数组是否已经有序
    if (is_sorted(array, unsorted_indices)) {
        return 0;
    }

    int ans = 0;
    size_t n = array.size();

    // 从数组末尾向前遍历
    for (size_t i = n - 1; i < array.size(); --i) {
        if (x > array[i]) {
            swap(array[i], x);
            ++ans;

            // 更新集合 unsorted_indices
            if (i != n - 1) {
                update_indices(array, unsorted_indices, i, i + 1);
            }
            if (i != 0) {
                update_indices(array, unsorted_indices, i - 1, i);
            }
        }

        // 如果集合 unsorted_indices 为空，表示数组已经有序
        if (unsorted_indices.empty()) {
            return ans;
        }
    }

    // 遍历结束后数组仍未有序
    return -1;
}

int main() {
	std::ios::sync_with_stdio(false);
    int n, x;
    cin >> n >> x;

    vector<int> array(n);
    for (int i = 0; i < n; ++i) {
        cin >> array[i];
    }

    cout << min_operations_to_sort(array, x) << endl;
    return 0;
}

Java

import java.util.*;
public class Main{
    public static void main(String[] args) {
        /**万诺coding：因为只能换到价值更低的礼物，所以每个位置上的数只能变大。
        最优方案是替换掉不符合条件的最小的数，在此情况下排序对照有多少个位置需要交换即可。*/
        Scanner in =new Scanner(System.in);
        int n =in.nextInt();
        long x =in.nextLong();
        long[] a =new long[n];
        long[] b=new long[n];
        for(int i=0;i<n;i++) {
            a[i]=in.nextLong();
            b[i]=a[i];
        }
        int left=0;
        while(left<n-1){
            if(a[left]<=a[left+1]) left++;
            else break;
        }
        if(left==n-1){
            System.out.print(0);
            return;
        }
        int right=left+1;
        int min =right;
        for(int i=right;i<n;i++) {
            b[i]=a[i];
            if(a[i]<a[min]) min=i;
        }
        b[min] =x;
        Arrays.sort(b,0,n);

        int cnt=0;
        for(int i=0;i<n;i++){
            if(a[i]>b[i]){
                System.out.print(-1);
                return;
            }
            if(a[i]!=b[i]) cnt++;
        }
        System.out.print(cnt);

    }
}

Python

def update(nums, unsorted_pos, x, y):
    if nums[x] > nums[y]:
        unsorted_pos.add(y)
    else:
        unsorted_pos.discard(y)

def get_unsorted(nums):
    unsorted_pos = set()
    for i in range(1, len(nums)):
        if nums[i] < nums[i - 1]:
            unsorted_pos.add(i)
    return unsorted_pos

def min_res(N, x, nums):
    unsorted_pos = get_unsorted(nums)

    if unsorted_pos.isdisjoint(set(range(1, len(nums)))):
        return 0
    
    res = 0
    for i in range(N - 1, -1 , -1):
        if x > nums[i]:
            nums[i], x = x, nums[i]
            res += 1
            if i != N - 1:
                update(nums, unsorted_pos, i, i + 1)
            if i != 0:
                update(nums, unsorted_pos, i - 1, i)
        
        if not unsorted_pos:
            return res

    return -1

if __name__ == "__main__":
    N, x = [int(c) for c in input().strip().split()]
    nums = [int(c) for c in input().strip().split()]

    print(min_res(N, x, nums))

题目内容

塔塔携带一件价值为$x$的礼物参加了一个节日派对。除多多外在场的有$n$个人，第$i$个人的当前持有的礼物价值为$a_i$。

塔塔可以和任意当前持有礼物价值比塔塔低的人交换礼物。

请问最少经过多少次交换，可以使得$n$个人持有的礼物价值形成单调不减的数列。

（$a_1≤a_2≤...≤a_n$）

输入描述

第一行输入两个数字$n$和$x$，$x$代表人数、和塔塔最多持有的礼物价值。

第二行$n$个数字$a_1,a_2,...a_n$,代表其他所有人最初持有的礼物价值

对于$60$%的数据，$1≤n≤10^3$

对于$100$%的数据，$1≤n≤2*10^6$，$1≤x,a_i≤10^9$

输出描述

输出一个数字,代表为了达成目标最少进行的交换次数。

如果无法达成目标则输出$-1$

样例1

输入

5 5
2 1 3 2 4

输出

3

说明

最初塔塔的礼物价值为$5$

第$1$次选择和第$5$个人交换。交换后塔塔的礼物价值为$4$，其他人为{$2，1，3，2，5$}

第$2$次选择和第$4$个人交换。交换后塔塔的礼物价值为$2$，其他人为{$2，1，3，4，5$}

第$3$次选择和第$2$个人交换。交换后塔塔的礼物价值为$1$，其他人为{$2，2，3，4，5$}