题目部分
题目 | 高效的任务规划 |
难度 | 难 |
题目说明 | 你有 n 台机器编号为 |
输入描述 | 第一行输入代表总共有 M 组任务数据(1 < M <= 10)。 每组数第一行为一个整数指定机器的数量 N (0 < N <= 1000)。 随后的 N 行每行两个整数,第一个表示 B (0 <= B <= 10000), 第二个表示 J (0 <= J <= 10000)。 每组数据连续输入,不会用空行分割,各组任务单独计时。 |
输出描述 | 对于每组任务,输出最短完成时间, 且每组的结果独占一行。 例如两组任务就应该有两行输出。 |
补充说明 | 无 |
------------------------------------------------------ | |
示例 | |
示例1 | |
输入 | 1 1 2 2 |
输出 | 4 |
说明 | 输出共 3 行数据,第 1 行代表只有 1 组数据;第 2 行代表本组任务只有 1 台机器;第 3 行代表本机器:配置需要 2 分钟,执行需要 2 分钟。输出 1 行数据,代表执行结果为 4 分钟。 |
示例2 | |
输入 | 2 2 1 1 2 2 3 1 1 2 2 3 3 |
输出 | 4 7 |
说明 | 第一行代表输入共 2 组数据, 2 - 4 行代表第一组数据,为 2 台机器的配置、执行信息(第 1 台机器:配置需要 1 分钟,执行需要 1 分钟;第 2 台机器:配置需要 2 分钟,执行需要 2 分钟)。5 - 8 行代表第二组数据,为 3 台机器的配置、执行信息(意义同上)。输出共 2 行,分别代表第 1 组任务共需要 4 分钟和第 2 组任务需要 7 分钟(先配置 3,在配置 2,最后配置 1,执行 1 分钟,共 7 分钟)。 |
解读与分析
题目解读:
每台机器只有配置了才能执行。而在同一个时间段只能执行一台机器的配置(配置串行执行),在配置完成后,任务即可执行。
求出执行完所有任务的时间。
分析与思路:
对于每一组数据,可以采取贪心算法,遍历所有的组合情况,求出每种情况所需要的时间,经比较,输出时间最小的数字。
此算法的时间复杂度为 O(),空间复杂度为 O()。
代码实现
Java代码
import java.util.Scanner;
/**
* 高效的任务规划
*
* @since 2023.10.25
* @version 0.1
* @author Frank
*
*/
public class EfficientTaskPlan {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String input = sc.nextLine();
int groupCnt = Integer.parseInt(input);
int[] outputValues = new int[ groupCnt ];
for( int i = 0; i < groupCnt; i ++ )
{
input = sc.nextLine();
int machineCnt = Integer.parseInt( input );
int [][] taskInfo = new int[machineCnt][2];
for( int j = 0; j < machineCnt; j ++ )
{
input = sc.nextLine();
String[] eachMachineStr = input.split( " " );
int[] eachMachine = new int[2];
eachMachine[0] = Integer.parseInt( eachMachineStr[0] );
eachMachine[1] = Integer.parseInt( eachMachineStr[1] );
taskInfo[j] = eachMachine;
}
int[] usedFlag = new int[taskInfo.length];
for( int j = 0; j < usedFlag.length; j ++ )
{
usedFlag[j] = 0;
}
outputValues[i] = caculateEachGroupTaskPlan( usedFlag, taskInfo, 0 );
}
for( int i = 0; i < groupCnt; i ++ )
{
System.out.println( outputValues[i] );
}
}
}
private static int caculateEachGroupTaskPlan( int[] usedFlag, int [][] taskInfo, int curTask ) {
int minTimeTake = Integer.MAX_VALUE;
for( int i = 0; i < taskInfo.length; i ++ )
{
if( usedFlag[i] == 1 )
{
continue;
}
int tmpConfig = taskInfo[i][0];
int tmpTask = taskInfo[i][1];
usedFlag[i] = 1;
int curTimeTake = tmpConfig + caculateEachGroupTaskPlan( usedFlag, taskInfo, tmpTask );
usedFlag[i] = 0;
if( curTimeTake <= curTask )
{
return curTask;
}
if( curTimeTake < minTimeTake )
{
minTimeTake = curTimeTake;
}
}
if( minTimeTake < curTask || minTimeTake == Integer.MAX_VALUE )
{
minTimeTake = curTask;
}
return minTimeTake;
}
}
JavaScript代码文章来源:https://www.toymoban.com/news/detail-724524.html
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {
while (line = await readline()) {
var groupCnt = parseInt(line);
var outputValues = new Array();
for (var i = 0; i < groupCnt; i++) {
line = await readline();
var machineCnt = parseInt(line);
var taskInfo = new Array();
for (var j = 0; j < machineCnt; j++) {
line = await readline();
var eachMachineStr = line.split(" ");
var eachMachine = new Array();
eachMachine[0] = parseInt(eachMachineStr[0]);
eachMachine[1] = parseInt(eachMachineStr[1]);
taskInfo[j] = eachMachine;
}
var usedFlag = new Array();
for (var j = 0; j < groupCnt; j++) {
usedFlag[j] = 0;
}
outputValues[i] = caculateEachGroupTaskPlan(usedFlag, taskInfo, 0);
}
for (var i = 0; i < groupCnt; i++) {
console.log(outputValues[i]);
}
}
}();
function caculateEachGroupTaskPlan(usedFlag, taskInfo, curTask) {
var minTimeTake = Number.MAX_VALUE;
for (var i = 0; i < taskInfo.length; i++) {
if (usedFlag[i] == 1) {
continue;
}
var tmpConfig = taskInfo[i][0];
var tmpTask = taskInfo[i][1];
usedFlag[i] = 1;
var curTimeTake = tmpConfig + caculateEachGroupTaskPlan(usedFlag, taskInfo, tmpTask);
usedFlag[i] = 0;
if (curTimeTake <= curTask) {
return curTask;
}
if (curTimeTake < minTimeTake) {
minTimeTake = curTimeTake;
}
}
if (minTimeTake < curTask || minTimeTake == Number.MAX_VALUE) {
minTimeTake = curTask;
}
return minTimeTake;
}
(完)文章来源地址https://www.toymoban.com/news/detail-724524.html
到了这里,关于华为OD机考算法题:高效的任务规划的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!