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

Jerry_zpl · 2025-07-07 20:11:34 · 题解

前言：本文原创，请勿抄袭。

现在有 n 个服务器，服务器 i 最多能处理 a_i 大小的数据。

接下来会有 k 条指令 b_k，指令 i 表示发送 b_i 的数据，需要你分配一个空闲的服务器。

请你算出一个序列 p_k 表示指令 i 的数据分配给服务器 p_i，且 p_k 的字典序最小；如果无法分配，输出 -1。

对于所有数据，n,k\leq 6，a_i,b_i \leq 10。

首先看数据范围,对于所有数据，n,k\leq 6，a_i,b_i \leq 10。那么，数据范围特别特别的小，而且考虑到需要分配，就可以采用我们的搜索。在这里，肯定用深度优先搜索。搜索的东西就是需要分配的东西 a_i。当然，不是所有的 a_i 都可以。在这里，如果 a_i≥b_x 才能分配，因为要有这个能力才可以啊。最后，我们只输出第一个答案即可，用个变量标记有没有答案即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn=15;
int n,k;
int a[maxn],b[maxn];
bool vis[maxn],flag=0;
int id[maxn];
void dfs(int x){
    if(x>k){
        if(!flag){
            for(int i=1;i<=k;i++){
                cout<<id[i]<<" ";
            }
        }
        flag=1;
        return ;
    }
    for(int i=1;i<=n;i++){
        if(a[i]>=b[x]&&vis[i]==0){
            vis[i]=true; 
            id[x]=i;
            dfs(x+1);
            id[x]=0;
            vis[i]=0;
        }
    }
}
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);
    if(flag==0){
        cout<<-1;
    }
    return 0;
}