题面描述:

题目要求我们对一批任务和执行机进行匹配调度，任务和执行机类型分别为CPU型(0)、IO型(1)和通用型(2)，其中通用型执行机可以执行任意类型的任务。每次任务和执行机按照优先级从高到低进行匹配，任务与执行机类型匹配则调度成功，执行机从数组中移除；若不匹配，则将执行机放回队列末尾。使用通用型执行机后，所有通用型执行机只能执行同一种类型任务。要求计算剩余的最小空置执行机数量。

题目思路

题目的重要条件是一旦2号机选择了转换为0号机或者1号机之后，所有的2号机都要做相同的转换。即所有的2号机最终要么变为0号机，要么变为1号机。同时也可以发现，不管是0号机和1号机怎么排列，都会被使用到，因为整个数组是循环的，即该题中的任务执行和机器的顺序无关，而只与0号机和1号机的数量有关。所以只需要讨论2号机变为0号机或者2号机变为1号机两种情况。然后计算该两种情况下机器的剩余情况。

当枚举2号机器变为0号机或者1号机之后，接下来的工作是模拟任务调度的过程，因为任务调度与机器是顺序无关，所以只需要统计出0,1号机的数量，当某时刻机器不足时直接break，从而求解出剩余的机器数量。

解决思路

由于问题的核心是要确定当所有通用型执行机被统一转换为 CPU 型或 IO 型时，剩余的最小空置执行机数量，因此问题可以简化为两种情况的讨论：

1. 通用型执行机全部转换为 CPU 型（0），即所有类型为 2 的执行机会被视为 0。
2. 通用型执行机全部转换为 IO 型（1），即所有类型为 2 的执行机会被视为 1。

任务调度过程与执行机的排列顺序无关，因此，我们只需要统计 0 号机和 1 号机的数量，在模拟调度过程中，当机器不足时停止并记录剩余的机器数量。

具体步骤

1. 输入数据：输入任务数组 tasks 和执行机数组 machines。
2. 枚举两种情况：枚举通用型执行机全部转换为 0 和全部转换为 1 两种情况。
3. 模拟任务调度：
   • 创建一个新的数组来存储机器类型的分布。
   • 根据当前的任务类型，逐个匹配机器。如果匹配成功，减少该类型机器的数量。如果无法匹配，则停止。
4. 记录结果：每种情况下记录剩余的空置执行机数量，最终返回两个方案中的最小值。

代码

python

# 计算最小机器剩余数 , x为2要变成的值
def calc_min_ops(task_arr, macine_arr, x , n):
    tmp = macine_arr.copy() # 用于计算的数组,需要复制一份,否则会改变原数组
    ans = n
    num = [0] * 2 # 统计每个机器的数量
    for i in range(n):
        if tmp[i] == 2: # 如果是2,则替换为x
            tmp[i] = x
        num[tmp[i]] += 1 # 统计每个机器的数量
    for i in range(n): # 从左到右遍历,直到遇到机器数量不够的位置退出
        num[task_arr[i]] -= 1
        if num[task_arr[i]] < 0:
            break
        ans -= 1
    return ans

def main():
    n = int(input())
    task_arr = list(map(int, input().split()))
    machine_arr = list(map(int, input().split()))
    ans1 = calc_min_ops(task_arr, machine_arr, 1 , n)
    ans2 = calc_min_ops(task_arr, machine_arr, 0 , n)
    print(min(ans1, ans2))

if __name__ == "__main__":
    main()

java

import java.util.Scanner;

class Main {
    static int n;
    public static void main(String[] args) {
        // 创建一个 Scanner 对象来读取用户输入
        Scanner sc = new Scanner(System.in);
        
        // 读取任务数量和机器数量
        n = sc.nextInt();
        
        // 创建数组来存储任务类型和机器类型
        int[] task_arr = new int[n];
        int[] machine_arr = new int[n];
        
        // 从用户那里读取任务类型和机器类型
        for (int i = 0; i < n; i++) {
            task_arr[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            machine_arr[i] = sc.nextInt();
        }
        
        // 计算将类型为 2 的机器转换为类型 1 或 0 所需的最小操作次数
        int ans1 = calcMinOps(task_arr, machine_arr, 1);
        int ans2 = calcMinOps(task_arr, machine_arr, 0);
        
        // 输出最小操作次数
        System.out.println(Math.min(ans1, ans2));
    }

    /**
     * 计算分配任务到机器所需的最小操作次数。
     * 
     * @param task_arr  一个表示任务类型的数组
     * @param machine_arr 一个表示机器类型的数组
     * @param x         将类型为 2 的机器转换为的目标类型（0 或 1）
     * @return 所需的最小操作次数
     */
    static int calcMinOps(int[] task_arr, int[] machine_arr, int x) {
        // 创建一个机器类型数组的副本, 以避免修改原始数组
        int[] converted_machine_arr = new int[n];
        
        // 将最大可能的操作次数初始化为 n
        int ans = n;
        
        // 初始化一个数组来跟踪每种类型机器的数量
        int[] machine_count = new int[2];
        
        // 将类型为 2 的机器转换为指定类型, 并更新机器数量
        for (int i = 0; i < n; i++) {
            converted_machine_arr[i] = machine_arr[i];
            if (converted_machine_arr[i] == 2) {
                converted_machine_arr[i] = x;
            }
            machine_count[converted_machine_arr[i]]++;
        }
        
        // 将任务分配给机器, 减少所需的操作次数
        for (int i = 0; i < n; i++) {
            machine_count[task_arr[i]]--;
            if (machine_count[task_arr[i]] < 0) {
                break;
            }
            ans--;
        }
        
        // 返回最小操作次数
        return ans;
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

static int n;

int calcMinOps(vector<int>& task_arr, vector<int>& machine_arr, int x) {
    // 创建一个机器类型数组的副本, 以避免修改原始数组
    vector<int> converted_machine_arr(machine_arr);
    
    // 将最大可能的操作次数初始化为 n
    int ans = n;
    
    // 初始化一个数组来跟踪每种类型机器的数量
    vector<int> machine_count(2, 0);
    
    // 将类型为 2 的机器转换为指定类型, 并更新机器数量
    for (int i = 0; i < n; i++) {
        if (converted_machine_arr[i] == 2) {
            converted_machine_arr[i] = x;
        }
        machine_count[converted_machine_arr[i]]++;
    }
    
    // 将任务分配给机器, 减少所需的操作次数
    for (int i = 0; i < n; i++) {
        machine_count[task_arr[i]]--;
        if (machine_count[task_arr[i]] < 0) {
            break;
        }
        ans--;
    }
    
    // 返回最小操作次数
    return ans;
}

int main() {
    // 创建一个 Scanner 对象来读取用户输入
    // 在C++中,我们使用标准输入流 cin 代替 Java 中的 Scanner
    
    // 读取任务数量和机器数量
    cin >> n;
    
    // 创建数组来存储任务类型和机器类型
    vector<int> task_arr(n);
    vector<int> machine_arr(n);
    
    // 从用户那里读取任务类型和机器类型
    for (int i = 0; i < n; i++) {
        cin >> task_arr[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> machine_arr[i];
    }
    
    // 计算将类型为 2 的机器转换为类型 1 或 0 所需的最小操作次数
    int ans1 = calcMinOps(task_arr, machine_arr, 1);
    int ans2 = calcMinOps(task_arr, machine_arr, 0);
    
    // 输出最小操作次数
    cout << min(ans1, ans2) << endl;
    
    return 0;
}

视频讲解

题目内容

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

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

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

解答要求

输入

输入共$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$，无法匹配，剩下的最小空置执行机数量为$1$