T2.DevOps任务调度(200分) - 华为机试真题题解

考试平台： 时习知

分值： 200分（第二题）

考试时间： 两小时（共3题）

题目描述

某Devops系统有一批并发任务需要匹配合适的执行机调度执行，任务和执行机都具有CPU型(用0表示)和 IO型(用1表示)的区别，此外还有一种通用型执行机(用2表示)，一批任务和执行机的类型分别用数组tasks、 machines表示, tasks[i]表示第i个任务，machines[i] 表示执行机的类型。每台CPU型、IO型执行机只能执行一个对应类型的任务，而通用型执行机既能执行CPU类型任务也能执行IO类型任务。

假设现有的匹配策略如下，任务需要按照优先级从高到低依次匹配执行机(i=0优先级最高), 因此每一轮选择任务数组头部(i=0) 的任务去匹配空置执行机数组头部(i=0)的执行机，若任务与执行机类型匹配，则代表该任务调度成功把该执行机从空置执行机数组中移除。若任务与执行机的类型不匹配，则将执行机放到执行机数组尾部，循环该过程直到任务全部匹配成功或当前任务无法被所有剩余空置执行机匹配。

现规定任意时刻都可以选择使用通用执行机，但一旦选择将某个类型的任务匹配通用型执行机，则所有通用型机器都只能用于执行该类型的任务，为了避免任务排队阻塞，请返回现有匹配策略下剩下的最小空置执行机数量。

输入

输入共3行

首行是一个正整数n，表示任务数量以及执行机数量

第2行包含n个垫数，以空格分隔，表示为任务数组tasks

第3行包含n个整数，以空格分隔，表示为空置执行机数组machines

数据范围: 1<=n<=100,0<=tasks[i]<=1，0<=machines[i]<=2。

输出

一行一个整数，代表当前匹配策略下剩下的最小空置执行机数量。

示例1

输入：
3
1 0 1
1 2 0

输出：
0

解释： 
第一轮 任务数组头部类型1，空置执行机数组头部类型1，匹配成功，任务数组变为[0,1],空置执行机数组变为[2,0]
第二轮 任务数组头部类型0，空置执行机数组头部类型2，若不选择类型2的执行机执行类型0的任务，将执行机放回数组尾部，任务数组不变为[0,1].空置执行机数组业为[0,2]
第三轮 任务数组头部类型0，空置执行机数组头部类型0，匹配成功，任务数组变为[1].空置执行机数组变为[2]
第四轮 任务数组头部类型1，空置执行机数组头部类型2，任务类型1选择匹配执行机类型2，因此剩下的最小空置执行机数量为0

示例2

输入：
4
1 0 1 1
1 0 2 0

输出：
1

解释： 
第一轮 任务数组头部类型1，空置执行机数组头部类型1，调度成功，任务数组变为[0,1,1].空置执行机数组变为[0,2,0]
第工轮 任务数组头部类型0，空置执行机数组头部类型0，调度成功，任务数组变为[1,1]空置执行机数组变为[2,0]
第三轮 任务数组头部类型1，空置执行机数组头部类型2，类型1的任务选择匹配类型2的执行机，任务数组变为[1],空置执行机数组变为[0]
第四轮 任务数组头部类型1，空置执行机数组头部类型0，无法匹