[传智杯 #3 决赛] 面试_代码007(未授权)

本文介绍: 请你算出一个序列 p k 表示指令 i 的数据分配给服务器 pi，且 pk 的字典序最小；接下来会有 k 条指令 bk，指令 i 表示发送 bi 的数据，需要你分配一个空闲的服务器。第 22 行输入 n 个正整数 ai，表示服务器 i 最多能处理的数据大小。现在有 n 个服务器，服务器 i 最多能处理 ai 大小的数据。第 33 行输入 k 个正整数 bi，表示指令 i。对于所有数据，n,k≤6，ai,bi≤10。第 1 条指令分给服务器 1；第 6 条指令分给服务器 5。

di sangan233 和 di sangan333 去面试了，面试官给了一个问题，热心的你能帮帮他们吗？

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

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

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

对于所有数据，n,k≤6，ai,bi≤10。

输入共 33 行。

6 6
1 9 1 9 8 1
1 1 4 5 1 4

1 3 2 4 6 5

#include &lt;iostream&gt;
using namespace std;
int n,k,a[7],b[7],p[7];//a数组是给的内存大小，b数组是要用的内存空间大小，p数组是用来存放最小字典序
bool f=1,u[7];//f用来标记是不是最小全排列，u数组是来记录每个数字是否被使用过
void dfs(int s){
    if(s==k+1){
        if(f){
            for(int i=1;i&lt;=n;i++)
                printf("%d ",p[i]);
        }//对符合条件的数据进行输出
        f=0;
        return;//跳出dfs深度优先搜索
    }
    for(int i=1;i&lt;=n;i++){
        if(a[i]&gt;=b[s]&amp;&amp;!u[i]){
            p[s]=i,u[i]=1;
            dfs(s+1);//继续深度优先搜索
            u[i]=0;//回溯，退回上一个
        }
    }
        return;//如果没有符合条件的数据，s不会满足s==k+1，直接退出，f依旧为1
}
int main(){
    cin&gt;&gt;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(f)
        puts("-1");
    return 0;
}