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

科技前沿 • 2025-01-29 14:10 • 阅读 62

大家好，我是讯享网，很高兴认识大家。

腾讯笔试题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()

讯享网

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

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

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

相关推荐