题目内容

调度器上有一组将调度的任务（$job$），大部分任务之间存在亲和关系，需要优先把具有亲和关系的任务调度到同一个核上面，不亲和的任务不能运行在同一个核上面；

现在给定一组待调度的任务（任务编号和任务执行时间），同时会给出任务之间不存在亲和关系的列表（未给出的默认是亲和关系）。请设计一个调度器，按照如下要求：

1、找出一组包含亲和任务数量最多的亲和调度任务组；

2、如果规则$1$有多个解，给出所有任务执行时间之和最小的。并输出该亲和调度任务组的所有任务执行时间之和。

亲和调度任务组定义：一组可以在同一核上面执行的亲和任务集合

解答要求

时间限制 $C/C++1000ms$ ，其他语言:$2000ms$ 内存限制 $C/C++256MB$，其他语言:$512MB$

输入

首行是一个整数$jobNum$，表示任务数量，任务编号$[1，jobNum]$，取值范围$[1,30]$

第二行$jobNum$个整数，表示每个任务的执行时间

第三行是一个整数$mutexNum$，表示不存在亲和关系的列表个数

接下来$mutexNum$行，每一行表示$1$对不亲和的任务编号，任务编号范围$[1,jobNum]$

输出

一个整数，表示所有任务的最短执行时间。

样例1

输入

3
2 3 10
1 
1 2

输出

12

解释:有$3$个待调度任务，任务$1$和任务$2$不亲和，不能在一个核上执行；

1.亲和调度任务组有：“任务$1$”“任务$2$”“任务$3$”，“任务$1$+任务$3$”，“任务$2$+任务$3$”；

2.包含任务数量最参的亲和调度任务组合有两种:“任务$1$+任务$3$”，或“任务$2$+任务$3$”；

3.两个任务的执行时间分别为$12$和$13$，选样执行时间较小的“任务$1$+任务$3$”，输出$12$。

样例2

输入

1
1
0

输出

1

解释:只有一个任务，返回这个任务的执行时间。

样例3

输入

3
2 3 10
3
1 2
2 3
1 3

输出

2

解释：有$3$个待调度任务，任务$1$和任务$2$、任务$2$和任务$3$、任务$1$和任务$3$不亲和，不能在一个核上执行；

1、亲和调度任务组有:“任务$1$”，“任务$2$”，“任务$3$”；

2、包含任务数量最多的亲和调度任务组合有$3$种:“任务$1$”，“任务$2$”，“任务$3$”；

3、$3$个场景的执行时间分别为$2、3、10$，选择执行时间较小的“任务$1$”，输出$2$。

【入门题】暴力拿分法2

本节课我们继续讨论骗分的方法。在前面章节我们学习了 DFS，也就是找遍所有的方法去得到正确答案，适用于范围小，因此我们可以用来骗分。

本题来自2024年8月21日华为机考真题。这里塔子哥给大家介绍一下华为机考：总共三道编程题，每道题的分值是(100,200,300)，通过华为机考需要至少150分。本题是秋招某次机考的最后一题(300分)。根据考生反映，使用本节课的骗分方法，我们可以拿到300 * 70% = 210 的高分，直接拿下机考!

题目理解

我们需要设计一个调度器，调度一组任务到不同的处理核上。任务之间存在亲和关系（默认情况下），即可以被调度到同一个核上；也存在不亲和关系（通过输入给出），即不能被调度到同一个核上。调度的目标是：

1. 最大化一个核上调度的亲和任务数量。
2. 在满足第1点的基础上，最小化这些任务的总执行时间。

最终，我们需要输出满足上述条件的任务组的总执行时间。

正确思路(感兴趣可以到本篇最下方进行查看)

• 思路1:最大团搜索算法
• 思路2:折半搜索(meet in the mid) + 子集dp

骗分思路（DFS + 2^n 枚举）

由于任务数量 jobNum 的范围为 [1, 30]，我们可以考虑使用深度优先搜索（DFS）结合位运算来枚举所有可能的任务组合。尽管 2^30（约 10 亿）个组合看起来庞大，但通过有效的剪枝和位运算优化，可以在合理的时间内解决此问题。

具体步骤：

1. 表示任务冲突：

   • 使用一个长度为 jobNum 的数组 conflict，其中 conflict[i] 是一个位掩码，表示任务 i 与哪些任务不亲和。如果 conflict[i] 的第 j 位为 1，表示任务 i 与任务 j 不亲和，不能同时调度到同一个核上。

2. DFS 枚举：

   • 从第一个任务开始，递归地选择是否将当前任务加入当前任务组。
   • 如果选择加入，需要确保当前任务与已选择的任务组中的所有任务没有冲突（通过位运算快速判断）。
   • 在每一步，记录当前任务组的大小和总执行时间，并更新全局最优解（最大任务数和最小总时间）。

3. 剪枝策略：

   • 如果当前任务组的大小加上剩余可选择的任务数量，无法超过当前已找到的最优任务组的大小，则可以提前剪枝，减少不必要的递归。

4. 优化位运算：

   • 通过使用位运算（如位掩码）来快速判断任务之间的冲突关系，提高运算效率。

Java实现

import java.util.*;

public class Main {
    
    static int jobNum;
    static int[] executionTime = new int[30];
    static long[] conflict = new long[30];
    static int maxCount = 0;
    static long minTotalTime = Long.MAX_VALUE;

    // DFS函数
    public static void dfs(int index, long currentMask, int count, long totalTime) {
        // 更新全局最优解
        if (count > maxCount || (count == maxCount && totalTime < minTotalTime)) {
            maxCount = count;
            minTotalTime = totalTime;
        }

        // 逐个尝试添加任务
        for (int i = index; i < jobNum; ++i) {
            // 检查任务i是否与当前任务组冲突
            if ((currentMask & (1L << i)) == 0) {
                // 检查任务i是否与已选任务冲突
                if ((conflict[i] & currentMask) == 0) {
                    // 选择任务i
                    dfs(i + 1, currentMask | (1L << i), count + 1, totalTime + executionTime[i]);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 输入任务数量
        jobNum = sc.nextInt();

        // 输入每个任务的执行时间
        for (int i = 0; i < jobNum; ++i) {
            executionTime[i] = sc.nextInt();
        }

        // 初始化冲突数组
        Arrays.fill(conflict, 0);

        // 输入不亲和关系的数量
        int mutexNum = sc.nextInt();
        for (int i = 0; i < mutexNum; ++i) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            conflict[u] |= (1L << v);
            conflict[v] |= (1L << u);
        }

        // 开始DFS
        dfs(0, 0, 0, 0);

        // 输出结果
        System.out.println(minTotalTime);

        sc.close();
    }
}

正确思路

思路1:最大团搜索算法

该问题就是最大团搜索算法的模板题。在搜索出每个最大团之后把团内节点的权值累加更新即可。

思路2:折半搜索(meet in the mid) + 子集dp

前置知识:二进制枚举技巧

一个最简单的思路就是$O(2^n)$枚举所有子集，但是这样复杂度超了。我们观察到$n = 30$ , 自然想到可以将集合分成两个部分$|A| = |B| = 15$ ， 这样我们就可以分别对$|A| , |B|$ 暴力计算最大亲和的子集了.

此时的问题在于：如何解决$A,B$ 集合之间的不亲和情况。

例如来自$A$集合的$1001$ , 那也就是第1,4个节点被选中，假设他们对于B集合的第2，3个点不亲和。那么也就是二进制状态$0110$不亲和。反过来也就是$1001$亲和。那么我们就只需要求出$B$集合在$1001$限定状态下最多能互相亲和的个数。

这个个数可以使用子集$dp$求出，如果s本身就是亲和的，那么$dp[s] = |s|$ , 也就是s中二进制1的个数。

否则，考虑$dp[s] = max(dp[x])$ , x是s的真子集。且x二进制中个数恰好比s少1。 复杂度$O(2^{|A|})$

最后枚举$A$集合的亲和子集，匹配B集合的dp ， 加起来即可。总复杂度$O(2^{\frac{n}{2}})$ 。

Java 实现（思路1）

import java.util.*;

public class Main {
    
    static int jobNum;
    static int[] times = new int[30];
    static Map<Integer, Set<Integer>> mutex = new HashMap<>();
    static int ans = 1;
    static int cost = Integer.MAX_VALUE;

    // 检查任务是否与已选择任务组冲突
    public static boolean check(int i, Set<Integer> usd) {
        for (int u : usd) {
            if (mutex.getOrDefault(u, new HashSet<>()).contains(i) || mutex.getOrDefault(i, new HashSet<>()).contains(u)) {
                return false;
            }
        }
        return true;
    }

    // DFS递归处理
    public static void dfs(int i, Set<Integer> usd, int time) {
        if (i >= jobNum) {
            if (ans <= usd.size()) {
                if (ans < usd.size()) {
                    ans = usd.size();
                    cost = time;
                } else if (ans == usd.size()) {
                    if (time < cost) {
                        cost = time;
                    }
                }
            }
            return;
        }
        if (usd.size() + jobNum - i + 1 < ans) return ;
        dfs(i + 1, usd, time);
        if (check(i, usd)) {
            usd.add(i);
            dfs(i + 1, usd, time + times[i]);
            usd.remove(i);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        jobNum = sc.nextInt();
        for (int i = 0; i < jobNum; i++) {
            times[i] = sc.nextInt();
        }

        int mutexNum = sc.nextInt();
        for (int i =

 0; i < mutexNum; i++) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            mutex.computeIfAbsent(a, k -> new HashSet<>()).add(b);
            mutex.computeIfAbsent(b, k -> new HashSet<>()).add(a);
        }

        Set<Integer> usd = new HashSet<>();
        dfs(0, usd, 0);

        System.out.println(cost);

        sc.close();
    }
}