9 solutions

  • 0
    @ 2024-10-27 11:06:10 
    def countnum(tasks,machines,t,n):
    tmp = machines.copy()
    nums = [0]*2
    ans = n
    for i in range(n):
        if tmp[i]==2:
            tmp[i]=t
        nums[tmp[i]]+=1
    for i in range(n):
        nums[tasks[i]]-=1
        if nums[tasks[i]]<0:
            break
        ans-=1
    return ans     

def main():
    n = int(input())
    tasks = list(map(int,input().split()))
    machines = list(map(int,input().split()))
    num1 = countnum(tasks,machines,1,n)
    num2 = countnum(tasks,machines,0,n)
    res = min(num1,num2)
    print(res)

if __name__ =='__main__':
    main()
    • 0
      @ 2024-10-20 21:31:41

      题面描述:

      题目要求我们对一批任务和执行机进行匹配调度，任务和执行机类型分别为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;
}
      • 0
        @ 2024-10-6 17:41:08

        低级方法：不动脑直接模拟全流程。但是不能确定循环次数，只能慢慢调大直到全部用例通过。

        import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        List<Integer> tasks = new ArrayList<>();
        List<Integer> machines = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            tasks.add(in.nextInt());
        }
        for (int i = 0; i < n; i++) {
            machines.add(in.nextInt());
        }

        // 通用机执行0号任务
        int m1 = doTasks(tasks, machines, n, 0);

        // 通用机执行1号任务
        int m2 = doTasks(tasks, machines, n, 1);

        System.out.println(Math.min(m1, m2));
        in.close();
    }

    private static int doTasks(List<Integer> tasks, List<Integer> machines, int n, int commonMachineType) {
        List<Integer> tasksTemp = new ArrayList<>(tasks);
        List<Integer> machinesTemp = new ArrayList<>(machines);
        int machineNum = n;
        int retryTimes = 0;
        while(retryTimes < 3*n && !tasksTemp.isEmpty() && !machinesTemp.isEmpty()) {
            if (Objects.equals(tasksTemp.getFirst(), machinesTemp.getFirst())) {
                tasksTemp.removeFirst();
                machinesTemp.removeFirst();
                machineNum--;
                continue;
            }
            if (machinesTemp.getFirst() == 2) {
                if (tasksTemp.getFirst() == commonMachineType) {
                    tasksTemp.removeFirst();
                    machinesTemp.removeFirst();
                    machineNum--;
                } else {
                    // 将当前机器置于最末端
                    machinesTemp.add(machinesTemp.getFirst());
                    machinesTemp.removeFirst();
                    retryTimes++;
                }
                continue;
            }
            // 将当前机器置于最末端
            machinesTemp.add(machinesTemp.getFirst());
            machinesTemp.removeFirst();
            retryTimes++;
        }
        return machineNum;
    }
}
        • 0
          @ 2024-10-3 20:49:57

          没有人的代码比我的更ez 因为根本不用分情况是往0号机还是1号机转，其实根据题意已经确定了…

          #include<bits/stdc++.h>
using namespace std;
int tsk[110],mch[110];
int a[3],b[3];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>tsk[i];
	for(int i=1;i<=n;i++)cin>>mch[i];
	for(int i=1;i<=n;i++){
		b[mch[i]]++;
	}
	int ans=n;
	for(int i=1;i<=n;i++){
		if(b[tsk[i]]>0)b[tsk[i]]--,ans--;
		else{
			if(b[2]){
				b[tsk[i]]+=b[2];
				b[2]=0;
				b[tsk[i]]--;
				ans--;
			}
			else break;
		}
	}
	cout<<ans;
	return 0;
}
          • 0
            @ 2024-9-10 0:51:45 
            #include <iostream>
#include <deque>

using namespace std;
int main()
{
    int total_number; cin >> total_number;
    deque<int> tasks(total_number);
    deque<int> machines(total_number);
    for(int i = 0; i < total_number; ++ i)
    {
        cin >> tasks[i];
    }
    for(int i = 0; i < total_number; ++ i)
    {
        cin >> machines[i];
    }

    deque<int> machines_i(machines);
    deque<int> tasks_i(tasks);
    for(int i = 0; i < total_number; ++i)
    {
        if(machines_i[i] == 2)
            machines_i[i] = 0;
    }
    
    deque<int> machines_o(machines);
    deque<int> tasks_o(tasks);
    for(int i = 0; i< total_number; ++i)
    {
        if(machines_o[i] == 2)
            machines_o[i] = 1;
    }

    int move_number_i = 0;
    while(move_number_i <= int(tasks_i.size()))
    {
        if(machines_i.front() == tasks_i.front())
        {
            machines_i.pop_front();
            tasks_i.pop_front();
            move_number_i = 0;
        }
        else
        {
            machines_i.push_back(machines_i.front());
            machines_i.pop_front();
            move_number_i ++;
        }
    }

    int move_number_o = 0;
    while(move_number_o <= int(tasks_o.size()))
    {
        if(machines_o.front() == tasks_o.front())
        {
            machines_o.pop_front();
            tasks_o.pop_front();
            move_number_o = 0;
        }
        else
        {
            machines_o.push_back(machines_o.front());
            machines_o.pop_front();
            move_number_o ++;
        }
    }

    if(move_number_i == 0 || move_number_o == 0)
    {
        cout << 0 << endl;
        return 0;
    }
    int left = tasks_i.size() > tasks_o.size() ? tasks_o.size() : tasks_i.size();
    cout << left << endl; 
    return 0;
}
            • 0
              @ 2024-8-25 16:17:43

              没有前面兄弟的代码简便

              from collections import Counter

n = int(input())
tasks = list(map(int, input().split()))
machines = list(map(int, input().split()))

def calc(ts, ms):
    i,j = 0,0
    count = 0
    length = len(ms)
    while i < len(ts) and j < len(ms):

        if ts[i] == ms[j]==0 or ts[i] == ms[j]==1:
            i+=1
            count=0
            ms.pop(j)
            length = len(ms)
            if length == 0:
                return 0
            j = j % length
        else:
            count+=1
            j = (j+1)% len(ms)

        if count == length:
            num_ms_2 = Counter(ms)[2]
            if num_ms_2 > 0:
                became_num =  ts[i]
                def b(n,became):
                    return became if n == 2 else n
                ms = [b(each,became_num) for each in ms]
                count = 0
            else:
                return len(ts)-i

result = calc(tasks, machines)
print(result)
              • 0
                @ 2024-8-25 12:34:37 
                from collections import deque, Counter
from itertools import count


# 使用counter记录下mach的数量，遍历每个task：如果还有此类mach就继续，没有就需要把mach=2的机器变成此类
def do():
    n = int(input())
    tasks = list(map(int, input().split()))
    machs = deque(list(map(int, input().split())))
    counter_mach = Counter(machs)
    for i in range(n):
        task = tasks[i]
        if counter_mach[task]:
            counter_mach[task] -= 1
            continue
        elif counter_mach[task] == 0 and counter_mach[2] > 0:
            counter_mach[task] = counter_mach[2] - 1
            counter_mach[2] = 0
        else:
            res = n - i
            print(res)
            return
    print(0)
    return


if __name__ == '__main__':
    do()
                • 0
                  @ 2024-8-23 15:56:26

                  注意：两个数据比较的步骤： 1.比较vector的长度 2.比较排序后的内容

                  
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct Info
{
    vector<int> rowdata;
    vector<int> data;
    int nums = 1;
};

bool ishave(vector<Info> &info, Info input)
{
    if(info.size() == 0) return false;
    for(int i = 0; i < info.size(); i++)
    {
        if(info[i].data.size() != input.data.size()) return false;
        for(int j = 0; j < info[i].data.size();j++)
        {
            if(info[i].data[j] != input.data[j])
            {
                break;
            }
            if(j == info[i].data.size()-1)
            {
                info[i].nums ++;
                return true;
            }   
        }
    }
    return false;
}

int main()
{
    int nums;
    int size;
    int input;
    cin >> nums;
    getchar();
    cin >> size;
    getchar();
    int datanum = (nums + size - 1) / size * size;
    vector<int> data(datanum,0);
    int size1 = size;
    for(int i = 0; i < nums; i++)
    {
        cin >> data[i];
    }
    vector<Info> res;
    int num1 = datanum/size;
    for(int i = 0; i < num1; i++)
    {
        Info data1;
        for(int j = 0; j < size; j ++)
        {
            if(size*i+j < nums)
            {
                data1.rowdata.push_back(data[size*i+j]);
                data1.data.push_back(data[size*i+j]);
            }
        }        
        sort(data1.data.begin(),data1.data.end());
        if(!ishave(res,data1))
        {
            res.push_back(data1);
        }
    }
    for(int i = 0; i < res.size(); i++)
    {
        for(int j : res[i].rowdata)
        {
            cout << j << " ";
        }
        cout << res[i].nums << " ";
    }
    return 0;
}
                  • 0
                    @ 2024-8-22 15:21:42

                    题目思路

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

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

                    代码

                    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

                    2024.8.21-秋招-第2题-Devops任务调度

                    Information

                    ID
                    102
                    Time
                    1000ms
                    Memory
                    256MiB
                    Difficulty
                    5
                    Tags
                    # Submissions
                    897
                    Accepted
                    182
                    Uploaded By
                    1. About
                    2. Contact Us
                    3. Privacy
                    4. Terms of Service
                    5. Copyright Complaint
                    6. Language
                    7. Legacy mode
                    8. Theme
                    2. 湘ICP备2023007293号
                    3. Worker 0, 37ms
                    4. Powered by Hydro v4.14.1 Community