华为OD机试之用户调度问题（Java源码）

news/2024/11/15 4:43:50/

用户调度问题

题目描述

在通信系统中，一个常见的问题是对用户进行不同策略的调度，会得到不同的系统消耗和性能。
假设当前有n个待串行调度用户，每个用户可以使用A/B/C三种不同的调度策略，不同的策略会消耗不同的系统资源。请你根据如下规则进行用户调度，并返回总的消耗资源数。
规则：

1.    相邻的用户不能使用相同的调度策略，例如，第1个用户使用了A策略，则第2个用户只能使用B或者C策略。

2.    对单个用户而言，不同的调度策略对系统资源的消耗可以归一化后抽象为数值。例如，某用户分别使用A/B/C策略的系统消耗分别为15/8/17。

3.    每个用户依次选择当前所能选择的对系统资源消耗最少的策略（局部最优），如果有多个满足要求的策略，选最后一个。

输入描述

第一行表示用户个数n

接下来每一行表示一个用户分别使用三个策略的系统消耗resA resB resC

输出描述

最优策略组合下的总的系统资源消耗数

用例

输入	3 15 8 17 12 20 9 11 7 5
输出	24
说明	1号用户使用B策略，2号用户使用C策略，3号用户使用B策略。系统资源消耗: 8 + 9 + 7 = 24。

题目解析

这个题目有的人使用迭代去做，迭代的思想相对来说简单些。每次取出一个资源，并把索引记录下来。往下迭代产生结果。
这个题为在解决的时候使用了动态规划算法。不熟悉的可以参考我的另一篇博客。
【算法】使用数位算法生成0至某个数之间的整数（for循环之外的另一种实现方式，蛮长见识的）
针对上述用例，用图可以展示为

其中黄线区域所连接的为不可达，因为题目要求相邻的用户不能使用相同的调度策略
最后计算每个叶子节点路径和并求出最小值即可。

示例代码java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;public class T49 {static int num[] = null;static int minResouce = Integer.MAX_VALUE;// 资源最小public static void main(String[] args) {Scanner sc = new Scanner(System.in);int userNo = Integer.parseInt(sc.nextLine());List<List<Integer>> resourceList = new ArrayList<List<Integer>>();for (int i = 0; i < userNo; i++) {List<Integer> resList = new ArrayList<Integer>();Arrays.stream(sc.nextLine().split(" ")).forEach(s -> resList.add(Integer.parseInt(s)));;resourceList.add(resList);}num = new int[userNo];System.out.println(resourceList);dfs(0, resourceList, -1);System.out.println(minResouce);}/*** * @param p            取第p个子列表* @param resourceList 所有的资源List* @param p1           上一个列表中取了哪一个索引*/public static void dfs(int p, List<List<Integer>> resourceList, int p1) {if (p >= resourceList.size()) {// 计算int sum = 0;for (int r : num) {sum += r;System.out.print(r + " ");}if (sum < minResouce) {minResouce = sum;}System.out.println();return;}List<Integer> itemList = resourceList.get(p);for (int i = 0; i < itemList.size(); i++) {if (i == p1)continue;num[p] = itemList.get(i);dfs(p + 1, resourceList, i); // i不能写成p 会产生错乱}}
}