一、题目描述
某公司研发了一款高性能AI处理器。每台物理设备具备8颗AI处理器，编号分别为0、1、2、3、4、5、6、7。编号0-3的处理器处于同一个链路中，编号4-7的处理器处于另外一个链路中，不通链路中的处理器不能通信，如下图所示。现给定服务器可用的处理器编号数组array，以及任务申请的处理器数量num，找出符合下列亲和性调度原则的芯片组合。如果不存在符合要求的组合，则返回空列表。
亲和性调度原则：
- 如果申请处理器个数为1，则选择同一链路，剩余可用的处理器数量为1个的最佳，其次是剩余3个的为次佳，然后是剩余2个，最后是剩余4个。
- 如果申请处理器个数为2，则选择同一链路剩余可用的处理器数量2个的为最佳，其次是剩余4个，最后是剩余3个。
- 如果申请处理器个数为4，则必须选择同一链路剩余可用的处理器数量为4个。
- 如果申请处理器个数为8，则申请节点所有8个处理器。
提示：
- 任务申请的处理器数量只能是1、2、4、8
- 编号0-3的处理器处于一个链路，编号4-7的处理器处于另外一个链路。
- 处理器编号唯一，且不存在相同编号处理器
二、输入描述
输入包含可用的处理器编号数组array，以及任务申请的处理器数量num两个部分。
第一行为array，第二行为num。
例如：
[0, 1, 4, 5, 6, 7]
1
表示当前编号为0、1、4、5、6、7的处理器可用。任务申请1个处理器。
0<= array.length <= 8
0<= array[i] <= 7
num in [1, 2, 4, 8]
三、输出描述
输出为组合列表，当array=[0, 1, 4, 5, 6, 7] ，num=1时，输出为[[0], [1]]
四、Python算法源码
cpu = []
string = input()
for ch in string:
if ch.isdigit():
cpu.append(ch)
cpu = list(map(int, cpu))
cpu = sorted(cpu)
num = int(input())
out = []
def is_duplicated(array, res):
if len(array) == 2 * res:
return True
else:
return False
def check(cpu, res):
line1 = []
line2 = []
for i in cpu:
if 0 <= i <= 3:
line1.append(i)
elif 4 <= i <= 7:
line2.append(i)
if len(line1) == len(line2): # both have the same number
if len(line1) == res:
for i in range(len(line2)):
line1.append(line2[i])
return line1
if len(line1) == res:
return line1
elif len(line2) == res:
return line2
else:
return False
sub_cpu = 0
if num == 1:
if check(cpu, 1):
sub_cpu = check(cpu, 1)
elif check(cpu, 3):
sub_cpu = check(cpu, 3)
elif check(cpu, 2):
sub_cpu = check(cpu, 2)
elif check(cpu, 4):
sub_cpu = check(cpu, 4)
else:
print('[]')
if sub_cpu:
for i in sub_cpu:
out.append([i])
print(out)
if num == 2:
if check(cpu, 2):
sub_cpu = check(cpu, 2)
if is_duplicated(sub_cpu, 2):
for i in range(2):
out.append(sub_cpu[i * 2:i * 2 + 2])
print(out)
else:
out.append(sub_cpu)
print(out)
elif check(cpu, 4):
sub_cpu = check(cpu, 4)
if is_duplicated(sub_cpu, 4):
for i in range(2):
line = sub_cpu[4 * i: 4 * i + 4]
for i in range(len(line)):
for j in range(i + 1, len(line)):
out.append([line[i], line[j]])
print(out)
else:
for i in range(len(sub_cpu)):
for j in range(i + 1, len(sub_cpu)):
out.append([sub_cpu[i], sub_cpu[j]])
print(out)
elif check(cpu, 3):
sub_cpu = check(cpu, 3)
if is_duplicated(sub_cpu, 3):
for i in range(2):
line = sub_cpu[3 * i: 3 * i + 3]
for i in range(len(line)):
for j in range(i + 1, len(line)):
out.append([line[i], line[j]])
print(out)
else:
for i in range(len(sub_cpu)):
for j in range(i + 1, len(sub_cpu)):
out.append([sub_cpu[i], sub_cpu[j]])
print(out)
else:
print('[]')
if num == 4:
if check(cpu, 4):
sub_cpu = check(cpu, 4)
if is_duplicated(sub_cpu, 4):
for i in range(2):
line = sub_cpu[4 * i: 4 * i + 4]
out.append(line)
print(out)
else:
out.append(sub_cpu)
print(out)
else:
print('[]')
if num == 8:
if len(cpu) == 8:
out.append(cpu)
print(out)
else:
print('[]')
五、效果展示
1、输入
[0, 1, 4, 5, 6, 7]
1
2、输出
[[0], [1]]
3、说明
根据第一条亲和性调度原则，在剩余两个处理器的链路（0,1,2,3）中选择处理器。由于只有0和1可用，则返回任意一颗处理器即可。
🏆下一篇：华为OD机试真题 Python 实现【相对开音节】【2022Q4 100分】，附详细解题思路
🏆本文收录于，华为OD机试（Python）真题（A卷+B卷）
刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，订阅后，专栏内的文章都可看，可加入华为OD刷题群（私信即可），发现新题目，随时更新，全天CSDN在线答疑。