(C卷,100分)- 用户调度问题（Java & JS & Python & C）

题目描述

在通信系统中，一个常见的问题是对用户进行不同策略的调度，会得到不同的系统消耗和性能。

假设当前有n个待串行调度用户，每个用户可以使用A/B/C三种不同的调度策略，不同的策略会消耗不同的系统资源。请你根据如下规则进行用户调度，并返回总的消耗资源数。

规则：

相邻的用户不能使用相同的调度策略，例如，第1个用户使用了A策略，则第2个用户只能使用B或者C策略。
对单个用户而言，不同的调度策略对系统资源的消耗可以归一化后抽象为数值。例如，某用户分别使用A/B/C策略的系统消耗分别为15/8/17。
每个用户依次选择当前所能选择的对系统资源消耗最少的策略（局部最优），如果有多个满足要求的策略，选最后一个。

输入描述

第一行表示用户个数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。

局部最优解法

本题第3个条件如下：

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

其中，每个用户选择得策略，只需要满足局部最优即可，比如题目用例：

第1个用户，局部最优应该选[15, 8, 17]中最小值8

第2个用户，由于受限于相邻用户不能选相同位置得策略，因此只能选择[12, 9]中局部最优的9

第3个用户，由于受限于相邻用户不能选相同位置得策略，因此只能选择[11, 7]中局部最优的7

因此，最终总消耗为：8 + 9 + 7 = 24

因此，有了这个局部最优的条件，本题的难度大大降低了。

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
let n;
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 1) {
    n = parseInt(lines[0]);
  }

  if (n != undefined && lines.length === n + 1) {
    lines.shift();
    const res = lines.map((line) => line.split(" ").map(Number));

    console.log(getResult(n, res));

    lines.length = 0;
  }
});

function getResult(n, res) {
  let last = -1;
  let sum = 0;

  for (let i = 0; i < n; i++) {
    last = getMinEleIdx(res[i], last);
    sum += res[i][last];
  }

  return sum;
}

function getMinEleIdx(arr, excludeIdx) {
  let minEleVal = Infinity;
  let minEleIdx = -1;

  for (let i = 0; i < arr.length; i++) {
    if (i == excludeIdx) continue;

    if (arr[i] <= minEleVal) {
      minEleVal = arr[i];
      minEleIdx = i;
    }
  }

  return minEleIdx;
}

Java算法源码

import java.util.Scanner;

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

    int n = sc.nextInt();

    int[][] res = new int[n][3];
    for (int i = 0; i < n; i++) {
      res[i][0] = sc.nextInt();
      res[i][1] = sc.nextInt();
      res[i][2] = sc.nextInt();
    }

    System.out.println(getResult(n, res));
  }

  public static int getResult(int n, int[][] res) {
    int last = -1;
    int sum = 0;

    for (int i = 0; i < n; i++) {
      last = getMinEleIdx(res[i], last);
      sum += res[i][last];
    }

    return sum;
  }

  public static int getMinEleIdx(int[] arr, int excludeIdx) {
    int minEleVal = Integer.MAX_VALUE;
    int minEleIdx = -1;

    for (int i = 0; i < arr.length; i++) {
      if (i == excludeIdx) continue;

      if (arr[i] <= minEleVal) {
        minEleVal = arr[i];
        minEleIdx = i;
      }
    }

    return minEleIdx;
  }
}

Python算法源码

import sys

# 输入获取
n = int(input())
res = [list(map(int, input().split())) for _ in range(n)]


def getMinEleIdx(arr, excludeIdx):
    minEleVal = sys.maxsize
    minEleIdx = -1

    for i in range(len(arr)):
        if i == excludeIdx:
            continue

        if arr[i] <= minEleVal:
            minEleVal = arr[i]
            minEleIdx = i

    return minEleIdx


# 算法入口
def getResult():
    last = -1
    total = 0

    for i in range(n):
        last = getMinEleIdx(res[i], last)
        total += res[i][last]

    return total


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>
#include <limits.h>

int getMinEleIdx(int arr[], int arr_size, int excludeIdx);
int getResult(int n, int res[][3]);

int main() {
    int n;
    scanf("%d", &n);

    int res[n][3];
    for(int i=0; i<n; i++) {
        scanf("%d %d %d", &res[i][0], &res[i][1], &res[i][2]);
    }

    printf("%dn", getResult(n, res));

    return 0;
}

int getResult(int n, int res[n][3]) {
    int last = -1;
    int sum = 0;

    for(int i=0; i<n; i++) {
        last = getMinEleIdx(res[i], 3, last);
        sum += res[i][last];
    }

    return sum;
}

int getMinEleIdx(int arr[], int arr_size, int excludeIdx) {
    int minEleVal = INT_MAX;
    int minEleIdx = -1;

    for(int i=0; i<arr_size; i++) {
        if(i == excludeIdx) continue;

        if(arr[i] <= minEleVal) {
            minEleVal = arr[i];
            minEleIdx = i;
        }
    }

    return minEleIdx;
}

全局最优解法（不符合本题要求，仅供学习参考）

如果本题没有下面这个要求

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

则要求的最少系统资源消耗数就是要全局最优的。

此时，我们可以通过回溯算法，求出所有组合情况，比较得出其中最小资源消耗的组合。

而本题回溯算法求解组合逻辑如下：

按照题目意思，用户是串行调度的，因此执行顺序不能改变，比如题目用例中，第一层必须选15 8 17，第二层必须选12 20 9，第三层必须选11 7 5。

另外，题目要求相邻层级间不能使用相同系统消耗策略，即：

第一层选了15，
第二层就不能选12，但是可以选20或9，如果第二层选了20，
则第三层就不能选7，但是可以选11或5.

因此回溯算法的递归层数、每层节点的筛选条件我们就都有了。

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
let m;
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 1) {
    m = parseInt(lines[0]);
  }

  if (m != undefined && lines.length === m + 1) {
    lines.shift();
    const res = lines.map((line) => line.split(" ").map(Number));
    const ans = [Infinity];
    dfs(res, m, 0, -1, 0, ans);
    console.log(ans[0]);

    lines.length = 0;
  }
});

function dfs(res, m, level, index, total, ans) {
  if (level == m) {
    ans[0] = Math.min(ans[0], total);
    return;
  }

  const r = res[level];
  for (let i = 0; i < r.length; i++) {
    if (i != index) {
      dfs(res, m, level + 1, i, total + r[i], ans);
    }
  }
}

Java算法源码

import java.util.Scanner;

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

    int m = sc.nextInt();

    int[][] res = new int[m][3];
    for (int i = 0; i < m; i++) {
      res[i][0] = sc.nextInt();
      res[i][1] = sc.nextInt();
      res[i][2] = sc.nextInt();
    }

    int[] ans = {Integer.MAX_VALUE};
    dfs(res, m, 0, -1, 0, ans);
    System.out.println(ans[0]);
  }

  public static void dfs(int[][] res, int m, int level, int index, int total, int[] ans) {
    if (level == m) {
      ans[0] = Math.min(ans[0], total);
      return;
    }

    int[] r = res[level];
    for (int i = 0; i < r.length; i++) {
      if (i != index) {
        dfs(res, m, level + 1, i, total + r[i], ans);
      }
    }
  }
}

Python算法源码

import sys

# 输入获取
m = int(input())
res = [list(map(int, input().split())) for _ in range(m)]


# 算法入口
def dfs(level, index, total, ans):
    if level == m:
        ans[0] = min(ans[0], total)
        return

    r = res[level]
    for i in range(len(r)):
        if i != index:
            dfs(level + 1, i, total + r[i], ans)


# 算法调用
ans = [sys.maxsize]
dfs(0, -1, 0, ans)
print(ans[0])

免责声明：

1、IT资源小站为非营利性网站，全站所有资料仅供网友个人学习使用，禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享，本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题，请立即告知本站，本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体，但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员，一律视为同意网站规定，本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文

3、原文链接：https://moreit.club/?blog=c%e5%8d%b7100%e5%88%86-%e7%94%a8%e6%88%b7%e8%b0%83%e5%ba%a6%e9%97%ae%e9%a2%98%ef%bc%88java-js-python-c%ef%bc%89，转载请注明出处。

2024华为OD机试题库