解题思路

给定长度为 $n$ 的序列 $a$ 和一个额外的数 $x$，每次只能选择一个满足 $a_i>x$ 的位置 $i$，将 $a_i$ 与 $x$ 交换。目标是使 $a$ 变为非递减序列，求最少操作次数，若无法完成则输出 -1。

动态规划建模

定义状态 $\mathrm{dp}[l][x_0]$ 表示当前已处理前缀，使得前缀末尾值为 $l$，当前 $x$ 的值为 $x_0$ 时所需的最少交换次数。为了压缩状态，注意：

• $l$ 必须是最后一次放入前缀的值（保证前缀非递减，只需与 $l$ 比较）。
• $x_0$ 是当前“背包”中的值。
• 初始状态为 $\mathrm{dp}[-1][x] = 0$，表示前缀为空，且初始 $x$ 值为给定的 $x$。

遍历序列中的每个元素 $v$ 时，尝试两种操作：

1. 不交换：若 $v \ge l$，则可以直接将 $v$ 放入前缀，状态转移到 $\mathrm{dp}[v][x_0]$，操作次数不变。
2. 交换：若 $v > x_0$ 且 $x_0 \ge l$，可与背包 $x_0$ 交换，先把 $x_0$ 放入前缀，再令背包变成 $v$，转移到 $\mathrm{dp}[x_0][v]$，操作次数加 1。

为了避免状态爆炸，在每一步对新状态进行剪枝：

• 对于同样的 $(l,x_0)$，只保留最小的操作次数。
• 对于 $x_0$ 较大的状态用单调队列或维护前缀最小操作次数来快速删除劣势状态。

最终在处理完所有元素后，答案为所有 $\mathrm{dp}[l][x_0]$ 中的最小值（若无可行状态则为 $\infty$ 即 -1）。

复杂度分析

• 序列长度 $n\le500$，$a_i,x\le500$。
• 理论上状态数为 $O(500\times500)=2.5\times10^5$，每步转移考虑两种操作，若不进行有效剪枝会 TLE。
• 通过对同一 $l$ 下的 $x_0$ 值按操作次数维护前缀最小值数组，可在 $O(1)$ 判断并剪掉较差状态。
• 整体时间近似 $O(n\cdot V\log V)$（其中 $V=500$），在常数较小情况下能通过。

代码

Python 版本

import sys
r = sys.stdin.readline
INF = 10**9

def solve():
    t = int(r())
    for _ in range(t):
        n, x = map(int, r().split())
        a = list(map(int, r().split()))
        # 状态字典：key=(l, x0)，value=最小操作次数
        dp = {(-1, x): 0}
        for v in a:
            new_dp = {}
            # 暴力尝试两种操作
            for (l, x0), cnt in dp.items():
                # 操作1：不交换
                if v >= l:
                    key = (v, x0)
                    new_dp[key] = min(new_dp.get(key, INF), cnt)
                # 操作2：交换
                if v > x0 and x0 >= l:
                    key = (x0, v)
                    new_dp[key] = min(new_dp.get(key, INF), cnt + 1)
            # 剪枝：对同一 l 只保留不同 x0 的最优 cnt
            # 并利用前缀最小值加速
            buckets = [INF] * 501
            filtered = {}
            # 排序保证按 l,x0,cnt 扫描
            for (l, x0), cnt in sorted(new_dp.items(), key=lambda it: (it[0][0], it[0][1], it[1])):
                # 如果已有更优的 x0' <= x0 对应 cnt' <= cnt，则跳过
                if min(buckets[:x0+1]) <= cnt:
                    continue
                filtered[(l, x0)] = cnt
                buckets[x0] = min(buckets[x0], cnt)
            dp = filtered
        ans = min(dp.values()) if dp else INF
        print(ans if ans < INF else -1)

if __name__ == "__main__":
    solve()

Java 版本

import java.io.*;
import java.util.*;

public class Main {
    static final int INF = 1_000_000_000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int[] a = Arrays.stream(br.readLine().split(" "))
                            .mapToInt(Integer::parseInt).toArray();
            // dp 状态使用 HashMap
            Map<Long, Integer> dp = new HashMap<>();
            // key 用 (l<<9)|x0 打包
            dp.put((((long)-1)<<9) | x, 0);
            for (int v : a) {
                Map<Long, Integer> ndp = new HashMap<>();
                for (Map.Entry<Long, Integer> e : dp.entrySet()) {
                    long key = e.getKey();
                    int l = (int)(key >> 9);
                    int x0 = (int)(key & 511);
                    int cnt = e.getValue();
                    // 不交换
                    if (v >= l) {
                        long nk = (((long)v)<<9) | x0;
                        ndp.put(nk, Math.min(ndp.getOrDefault(nk, INF), cnt));
                    }
                    // 交换
                    if (v > x0 && x0 >= l) {
                        long nk = (((long)x0)<<9) | v;
                        ndp.put(nk, Math.min(ndp.getOrDefault(nk, INF), cnt+1));
                    }
                }
                // 剪枝
                int[] best = new int[501];
                Arrays.fill(best, INF);
                Map<Long, Integer> filtered = new HashMap<>();
                List<long[]> entries = new ArrayList<>();
                for (Map.Entry<Long, Integer> e : ndp.entrySet()) {
                    entries.add(new long[]{e.getKey(), e.getValue()});
                }
                entries.sort(Comparator.<long[]>comparingLong(o -> ((o[0]>>9)&511))
                                  .thenComparingLong(o -> (o[0]&511))
                                  .thenComparingLong(o -> o[1]));
                for (long[] rec : entries) {
                    long key = rec[0];
                    int cnt = (int)rec[1];
                    int l = (int)(key>>9), x0 = (int)(key&511);
                    int minPrev = INF;
                    for (int i = 0; i <= x0; i++) minPrev = Math.min(minPrev, best[i]);
                    if (minPrev <= cnt) continue;
                    filtered.put(key, cnt);
                    best[x0] = Math.min(best[x0], cnt);
                }
                dp = filtered;
            }
            int ans = dp.isEmpty() ? INF : Collections.min(dp.values());
            System.out.println(ans < INF ? ans : -1);
        }
    }
}

C++ 版本

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; cin >> t;
    while (t--) {
        int n, x;
        cin >> n >> x;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];

        // 使用 map< pair<int,int>, int >
        map<pair<int,int>, int> dp;
        dp[{ -1, x }] = 0;

        for (int v : a) {
            map<pair<int,int>, int> ndp;
            for (auto &it : dp) {
                int l = it.first.first;
                int x0 = it.first.second;
                int cnt = it.second;
                // 不交换
                if (v >= l) {
                    auto key = make_pair(v, x0);
                    ndp[key] = min(ndp.count(key) ? ndp[key] : INF, cnt);
                }
                // 交换
                if (v > x0 && x0 >= l) {
                    auto key = make_pair(x0, v);
                    ndp[key] = min(ndp.count(key) ? ndp[key] : INF, cnt+1);
                }
            }
            // 剪枝
            vector<int> best(501, INF);
            map<pair<int,int>, int> filtered;
            // 将 ndp 条目按 (l,x0,cnt) 排序
            vector<tuple<int,int,int>> entries;
            for (auto &it : ndp)
                entries.emplace_back(it.first.first, it.first.second, it.second);
            sort(entries.begin(), entries.end());
            for (auto &tp : entries) {
                int l, x0, cnt;
                tie(l, x0, cnt) = tp;
                int minPrev = *min_element(best.begin(), best.begin()+x0+1);
                if (minPrev <= cnt) continue;
                filtered[{l,x0}] = cnt;
                best[x0] = min(best[x0], cnt);
            }
            dp.swap(filtered);
        }
        int ans = INF;
        for (auto &it : dp) ans = min(ans, it.second);
        cout << (ans < INF ? ans : -1) << "\n";
    }
    return 0;
}

题目内容

多多现在需要你帮助解决一个难题，多多得到了一个由 $n$ 个整数 $a_1,a_2,…,a_n$ 构成的序列 $a$ 和额外的一个整数 $x$，多多的任务是排序序列 $a$ 使其变为正序列，其中只要序列 $a$ 满足 $a_1 \leq a_2\leq … \leq a_n$ 就认为是一个正序列。

为了让序列 $a$ 变成正序列，多多被允许可以重复多次做这样一个操作：选择序列 $a$ 中的一个整数 $a_i(1 \leq i\leq n)$ 且满足 $a_i>x$，然后交换 $a_i$ 和 $x$。

例如对于序列 $a=[0,2,3,5,4]$ 和 $x=1$，可以通过 $3$ 次上述操作使得序列 $a$ 变成一个正序列。

$1.$选择 $i= 2$ (满足 $a_2>x$)，交换后状态为 $a=[0,1,3,5,4],x=2$;

$2.$选择 $i=3$ (满足 $a_3>x$)，交换后状态为 $a=[0,1,2,5,4],x=3$;

$3.$选择 $i=4$ (满足 $a_4>x$)，交换后状态为 $a=[0,1,2,3,4],x=5$。

多多现在需要你帮助计算出对于一个序列 $a$ 最少需要多少次上述操作能够使得其变成正序列。

输入描述

第一行包含一个整数 $t(1\leq t\leq 500)$，表示有 $t$ 组测试数据。

每组测试数据包含两行。第一行包含两个数字 $n$ 和 $x(1\leq n\leq 500,1\leq x\leq 500)$，$n$ 表示序列的长度。

接下来第二行包含 $n$ 个整数 $a_1, a_ 2,…, a_n$，其中对于仼意 $1\leq i\leq n$ 都有 $0\leq a_i\leq 500$。

输出描述

对于每组测试数据输出一个整数，代表将原序列变为正序列所需要的最小操作次数，如果无法将原序列变为正序列则输出 $-1$。

示例1

输入

6
4 1
2 3 5 4
5 6
1 1 3 4 4
1 10
2
2 10
11 9
2 10
12 11
5 18
81 324 218 413 324

输出

3
0
0
-1
1
3