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

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

现在有

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

才能分配，因为要有这个能力才可以啊。最后，我们只输出第一个答案即可，用个变量标记有没有答案即可。

CPP

#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;
}

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

文章操作

相关推荐

评论

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