本文介绍: 请你算出一个序列 pk 表示指令 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。
题目背景
disangan233 和 disangan333 去面试了,面试官给了一个问题,热心的你能帮帮他们吗?
题目描述
现在有 n 个服务器,服务器 i 最多能处理 ai 大小的数据。
接下来会有 k 条指令 bk,指令 i 表示发送 bi 的数据,需要你分配一个空闲的服务器。
请你算出一个序列 pk 表示指令 i 的数据分配给服务器 pi,且 pk 的字典序最小;如果无法分配,输出 “-1″。
输入格式
输入共 33 行。
第 11 行输入 22 个正整数 n,k。
第 22 行输入 n 个正整数 ai,表示服务器 i 最多能处理的数据大小。
输出格式
输出共 11 行 k 个正整数 p1…pk,或者输出 “-1″。
输入输出样例
输入 #1复制
6 6 1 9 1 9 8 1 1 1 4 5 1 4
输出 #1复制
1 3 2 4 6 5
说明/提示
样例解释
第 1 条指令分给服务器 1;
第 2 条指令分给服务器 3;
第 3 条指令分给服务器 2;
第 4 条指令分给服务器 4;
第 5 条指令分给服务器 6;
第 6 条指令分给服务器 5。
思路分享:这个是一个深度优先搜索的问题,然后我们先把大问题化成小问题,先弄都弄4个数字, 1 9 1 9和 1 1 4 5。下面慢慢推他的图,下面是我分享的过程图,当遇到×时候,就回退,直到找到满足条件且s==k+1,即为全部找到了。
#include <iostream>
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<=n;i++)
printf("%d ",p[i]);
}//对符合条件的数据进行输出
f=0;
return;//跳出dfs深度优先搜索
}
for(int i=1;i<=n;i++){
if(a[i]>=b[s]&&!u[i]){
p[s]=i,u[i]=1;
dfs(s+1);//继续深度优先搜索
u[i]=0;//回溯,退回上一个
}
}
return;//如果没有符合条件的数据,s不会满足s==k+1,直接退出,f依旧为1
}
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(f)
puts("-1");
return 0;
}
原文地址:https://blog.csdn.net/qq_73062949/article/details/134770787
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_37146.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。