华为OD机考算法题:高效的任务规划

这篇具有很好参考价值的文章主要介绍了华为OD机考算法题:高效的任务规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目部分

题目 高效的任务规划
难度
题目说明

你有 n 台机器编号为 1 ~ 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代码

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 华为OD机考算法题:区块链文件转储系统

    题目部分 解读与分析 代码实现 题目 区块链文件转储系统 难度 难 题目说明 区块链底层存储是一个链式文件系统,由顺序的N个文件组成,每个文件的大小不一,依次为F1、F2……Fn。随着时间的推移,所占存储会越来越大。 云平台考虑将区块链按文件转储到廉价的SATA盘,只

    2024年02月08日
    浏览(36)
  • 华为OD机考算法题:MVP争夺战

    题目部分 解读与分析 代码实现 题目 MVP争夺战 难度 易 题目说明 在星球争霸篮球赛对抗赛中,强大的宇宙战队,希望每个人都能拿到MVP。 MVP的条件是,单场最高分得分获得者,可以并列,所以宇宙战队决定在比赛中,尽可能让更多的队员上场,且让所有有得分的队员得分都

    2024年02月09日
    浏览(33)
  • 华为OD机考算法题:数字加减游戏

    题目部分 解读与分析 代码实现 题目 数字加减游戏 难度 难 题目说明 小明在玩一个数字加减游戏,只使用加法或者减法,将一个数字 s 变成数字 t 。 每个回合,小明可以用当前的数字加上或减去一个数字。 现在有两种数字可以用来加减,分别为 a, b (a≠b),其中 b 没有使用

    2024年02月09日
    浏览(39)
  • 【华为OD机考 统一考试机试C卷】高效货运(C++ Java JavaScript Python C语言)

    目前在考C卷,经过两个月的收集整理, C卷真题已基本整理完毕 抽到原题的概率为2/3到3/3, 也就是最少抽到两道原题。 请注意:大家刷完C卷真题,最好要把B卷的真题刷一下,因为C卷的部分真题来自B卷。 另外订阅专栏还可以联系笔者开通在线OJ进行刷题,提高刷题效率。

    2024年02月02日
    浏览(44)
  • 华为OD机考算法题:阿里巴巴找黄金宝箱(1)

    题目 阿里巴巴找黄金宝箱(1) 难度 易 题目说明 一贫如洗的樵夫阿里巴巴在去砍柴的路上,无意中发现了强盗集团的藏宝地,藏宝地有编号从 0 ~ N 的箱子,每个箱子上面贴有一个数字,箱子中可能有一个黄金宝箱。 黄金宝箱满足排在它之前的所有箱子数字和等于排在它之

    2024年02月07日
    浏览(45)
  • 华为OD机考算法题:根据某条件聚类最少交换次数

    题目部分 解读与思路 代码实现 题目 根据某条件聚类最少交换次数 难度 难 题目说明 给出数字K,请输出所有结果小于K的整数组合到一起的最少交换次数。 组合一起是指满足条件的数字相邻,不要求相邻后在数组中的位置。 数据范围 -100 =K = 100 -100 = 数组中数值 = 100 输入描

    2024年02月09日
    浏览(36)
  • 【华为OD机考 统一考试机试C卷】特殊的加密算法(C++ Java JavaScript Python C语言)

    真题目录:华为OD机考机试 真题目录( D卷 +C卷 + B卷 + A卷) + 考点说明 在线OJ:点击立即刷题,模拟真实机考环境 华为OD面试真题精选:华为OD面试真题精选 有一种特殊的加密算法,明文为一段数字串,经过密码本查找转换,生成另一段密文数字串。 规则如下: 明文为一段

    2024年04月16日
    浏览(45)
  • 华为OD机试题中 动态规划和贪心算法例题

    在 ACM 比赛中,有许多常见的编程算法和数据结构经常被使用。本系列博客会罗列各种常见算法,以及其代表性例题。 这部分内容可以用于类似华为 OD 机考学习。 动态规划是一种将复杂问题分解为简单子问题并使用子问题的解来构建更大问题的方法。它通常用于解决最长公

    2024年01月16日
    浏览(48)
  • 华为OD机考--【磁盘容量排序】

    ■  题目描述 【磁盘容量排序】 磁盘的容量单位常用的有M,G,T这三个等级,它们之间的换算关系为1T = 1024G,1G = 1024M,现在给定n块磁盘的容量, 请对它们按从小到大的顺序进行稳定排序,例如给定5块盘的容量,1T,20M,3G,10G6T,3M12G9M排序后的结果为20M,3G,3M12G9M,1T,

    2024年02月14日
    浏览(40)
  • 【华为OD机考 统一考试机试C卷】素数之积/RSA加密算法(C++ Java JavaScript Python C语言)

    目前在考C卷,经过两个月的收集整理, C卷真题已基本整理完毕 抽到原题的概率为2/3到3/3, 也就是最少抽到两道原题。 请注意:大家刷完C卷真题,最好要把B卷的真题刷一下,因为C卷的部分真题来自B卷。 另外订阅专栏还可以联系笔者开通在线OJ进行刷题,提高刷题效率。

    2024年03月21日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包