双核处理问题

发表于 | 分类于 |
字数统计 566 | 阅读时长 2

题目

一种双核CPU的两个核能够同时的处理任务，现在有n个已知数据量的任务需要交给CPU处理，假设已知CPU的每个核1秒可以处理1kb，每个核同时只能处理一项任务。n个任务可以按照任意顺序放入CPU进行处理，现在需要设计一个方案让CPU处理完这批任务所需的时间最少，求这个最小的时间。

输入描述

输入包括两行：
第一行为整数n(1 ≤ n ≤ 50)
第二行为n个整数lengthi，表示每个任务的长度为length[i]kb，每个数均为1024的倍数。

输出描述

输出一个整数，表示最少需要处理的时间

输入例子

5
3072 3072 7168 3072 1024

输出例子

9216

思考

首先得理解题意，1s单核可以处理1kb，length数组里面的存放的是一个个长度为1024倍数单位为kb的值，求设计方案，让cpu处理这批任务所需时间最短，就是给一个任务分配的顺序以及给cpu core A还是cpu core B。
稍微想一想，我想到了这个东东

是不是很像！
只不过是两行的俄罗斯方块，尽可能让他的高度最短～～～
那么这样就好做了，方案如下

先将数组倒序排序
再按顺序分别填入cpu core A(以下用a代替) 和 cpu core B(以下用b代替),每填一个，就判断一下，a的长度和b的长度谁长，判断之后，下一个任务填入短的那个cpu core，就这么下去，最后再判断一下左右两个cpu core,选长的一个作为最终的结果。

解决方案


TALK IS CHEAP,SHOW ME THE CODE!
最近在学python，机子上没有装c环境，偷个懒，便用python写了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# -*- coding: utf-8 -*-
#n:个数
#length[]：数组
n = input("n:")
timesA = 0
timesB = 0
length = []
times = 0;
for i in range(n):
    y = input(str(i)+":")
    length.append(y/1024)
#先对length数组内容排序
length.sort()
length.reverse()
#比较函数
def compare(a,b):
    if a >= b:
        return a
    else:
        return b
#填入动作
def send(data):
    global timesA,timesB
    if timesA <= timesB:
        timesA += data
    else :
        timesB += data
for item in length:
    send(item)
times = compare(timesA,timesB)
print times*1024

最后上个结果图