题解：P8838 [传智杯 #3 决赛] 面试

· · 题解

一道搜索题。

思路分析

用 dfs 暴力枚举即可，由于 n,k \le 6，所以解法不会超时。

dfs 每一个指令，匹配每一个服务器，只要找到第一种解，就是字典序最小的，因为每一层遍历都是从小到大的。

1. 确定递归边界：

当 k 个指令都匹配完后，就找到了正解。

if (x == k + 1) { // 指令都匹配完了
    for (int i = 1; i <= n; i++) cout << ans[i] << " "; // 输出正解序列
    exit(0); // 结束程序
}

2. 循环匹配服务器：

用 for 循环给当前指令匹配每一个服务器。

只要当前服务器 a_i 能处理当前指令 b_x（a_i \ge b_x）并且当前服务器没有被其他指令匹配过，就可以匹配。

for (int i = 1; i <= n; i++) // 寻找合适的服务器
    if (!vis[i] && a[i] >= b[x]) { // 满足匹配条件
        vis[i] = true; // 标记为匹配过
        ans[x] = i; // 记录答案
        dfs(x + 1); // dfs 下一层
        vis[i] = false; // 回溯
    }

最后判无解。只要在 dfs 时没找到正解，就是无解，输出 -1。

完整 AC 代码

#include<iostream>
using namespace std;
int n, k;
int a[10], b[10];
int ans[10], vis[10];
void dfs(int x) {
    if (x == k + 1) {
        for (int i = 1; i <= n; i++) cout << ans[i] << " ";
        exit(0);
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i] && a[i] >= b[x]) {
            vis[i] = true;
            ans[x] = i;
            dfs(x + 1);
            vis[i] = false;
        }
}
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= k; i++) cin >> b[i];
    dfs(1); // 暴力枚举
    cout << -1; // 无解
    return 0;
}