腾讯笔试题之m台机器完成n个任务调度问题(Python实现)

腾讯笔试题m台机器完成n个任务调度最大收益问题

问题描述:

m个任务,第i个任务需要Xi的时间去完成,难度为Yi。

有m台机器,第i台机器最长工作时间为Zi,机器等级为Wi。

对于一个任务只能交由一台机器完成,任务被完成的条件为:任务所需时间Xi小于机器最长工作时间Zi,任务难度Yi小于等于机器等级Wi。

任务被第i台机器完成的收益为200*Xi+3*Yi。

一台机器只能分配一个任务。

想完成尽可能多的任务,若有多种方案,求收益最大的那个?

输入:

共m+n+1行

第一行:n m

接下来n行:Zi Wi

接下来m行:Xi Yi

输出:

任务完成数 收益

示例:

输入

1 2

100 3

100 2

100 1

输出

1 20006

解题思路:贪心求解
– 收益只有完成的任务的x,y有关,且x,y越大,收益越大
– 所以要优先完成x更大的任务,若x相等,要优先完成y大的任务
– 即任务要按x从大到小排序,若x相等则按y从大到小排序
– 机器反之,从小到大排序。
遍历机器,对每个机器选取最长时间和最高等级的任务去完成

Python完整代码和相关注释如下:

#coding:utf-8
import sys

class element():
    # 定义机器和任务类
    def __init__(self, time, level):
        self.time = time
        self.level = level
    def __gt__(self, other):
        # 运算符重载,方便排序
        if self.time == other.time:
            return self.level > other.level
        return self.time > other.time

def solve():
    # 接收数据
    nm = list(map(int, sys.stdin.readline().split()))
    n, m = nm[0], nm[1]
    # 机器
    machine = []
    for i in range(n):
        time_level = list(map(int, sys.stdin.readline().split()))
        machine.append(element(time_level[0], time_level[1]))
    # 任务
    task = []
    for i in range(m):
        time_level = list(map(int, sys.stdin.readline().split()))
        task.append(element(time_level[0], time_level[1]))
    # 排序
    machine = sorted(machine)
    task = sorted(task)
    # 任务数和收益
    count = 0
    benifit = 0
    # 遍历机器
    for i in range(len(machine)):
        # 选取可完成的最长时间和最高等级任务
        j = 0
        while j<len(task) and machine[i].time >= task[j].time and machine[i].level >= task[j].level:
            j += 1
        # 如果有符合的任务计算收益
        if j > 0:
            count += 1
            j-=1
            benifit += task[j].time*200 + task[j].level*3
            task.pop(j)
    # 输出结果
    print(count, benifit)

if __name__ == "__main__":
    solve()

如有错误,欢迎交流和指正~

    原文作者:ZzzMxin
    原文地址: https://blog.csdn.net/qq_34178562/article/details/79889108
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞