首页 > 试题广场 >

工作安排

[编程题]工作安排
  • 热度指数：2363 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
现在有n位工程师和6项工作(编号为0至5)，现在给出每个人能够胜任的工作序号表(用一个字符串表示，比如：045，表示某位工程师能够胜任0号，4号，5号工作)。现在需要进行工作安排，每位工程师只能被安排到自己能够胜任的工作当中去，两位工程师不能安排到同一项工作当中去。如果两种工作安排中有一个人被安排在的工作序号不一样就被视为不同的工作安排，现在需要计算出有多少种不同工作安排计划。

输入描述:
输入数据有n+1行： 第一行为工程师人数n(1 ≤ n ≤ 6) 接下来的n行，每行一个字符串表示第i(1 ≤ i ≤ n)个人能够胜任的工作(字符串不一定等长的)


输出描述:
输出一个整数，表示有多少种不同的工作安排方案
示例1

输入

6 012345 012345 012345 012345 012345 012345

输出

720
算法知识视频讲解
添加回答
Python
牛客558275203号头像 牛客558275203号 
n = int(input())
canDo = [input() for _ in range(n)] 
done = [False] * 6

def solve(i):
    
    if i == n:
        return 1
    
    res = 0
    for k in range(6):
        if not done[k] and (str(k) in canDo[i]):
            done[k] = True
            res += solve(i+1)
            done[k] = False
    return res

print(solve(0))

回溯法Python3版本。
编辑于 2020-04-07 11:26:27 回复(0)
Python
绝无*仅有头像 绝无*仅有
def getData():
    n = eval(input("请输入工程师人数:"))
    engineerDic = {}
    for m in range(1,n+1):
        job = input("第%d位工程师胜任工作:"%m)
        engineerDic[m]=job
    return engineerDic

def workArray(workList,i):
    global num
    if i < len(engineerDic.keys())+1:
        works = engineerDic[i]
        for work in works:
            if eval(work) in workList:
                workList.remove(eval(work))
                i += 1
                workArray(workList,i)
                i-=1
                workList.append(eval(work))
    else:
        num+=1
engineerDic = getData()
num = 0
i = 1
workList = [0, 1, 2, 3, 4, 5]
workArray(workList,i)
print(num)
发表于 2017-11-18 17:34:54 回复(0)
提交观点

问题信息

模拟 递归
来自：网易2017春招笔试真...
难度：
2条回答 9082浏览

热门推荐

通过挑战的用户

相关试题

工作安排

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号