首页 > 试题广场 >

双核处理

[编程题]双核处理
  • 热度指数：11779 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
一种双核CPU的两个核能够同时的处理任务，现在有n个已知数据量的任务需要交给CPU处理，假设已知CPU的每个核1秒可以处理1kb，每个核同时只能处理一项任务。n个任务可以按照任意顺序放入CPU进行处理，现在需要设计一个方案让CPU处理完这批任务所需的时间最少，求这个最小的时间。

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


输出描述:
输出一个整数，表示最少需要处理的时间
示例1

输入

5 3072 3072 7168 3072 1024

输出

9216
算法知识视频讲解
添加回答
Python
Fzldq头像 Fzldq
Python细节：两者比较不要用max，用main包一下会快很多，剪枝 
def main():
    n = int(input())
    lst = list(map(lambda x: int(x) >> 10, input().split()))

    s = sum(lst) // 2
    dp = [0] * (s + 1)
    for i in range(n):
        for j in range(s, -1, -1):
            if j >= lst[i]:
                tmp = dp[j - lst[i]] + lst[i]
                if dp[j] < tmp:
                    dp[j] = tmp
            else:
                break
    print(max(dp[s], sum(lst) - dp[s]) << 10)


if __name__ == '__main__':
    main()


编辑于 2020-07-18 01:49:54 回复(0)
Python
charles7头像 charles7 
n = input()
length =[int(i)//1024 for i in input().strip().split()] 

half = sum(length)/2
h = set(length) 
 
for i in length: 
	for j in list(h): 
 		h.add(i+j)  
 
h = [i for i in h if i>=half] 
 
print(min(h)*1024)

发表于 2017-08-09 01:17:18 回复(0)
Python
周昆头像 周昆 
N = int(raw_input())
length = map(lambda x: int(x)//1024, raw_input().split())
V = sum(length) // 2
f = [0] * (V + 1)
for i in range(N):
	v = V
	while v >= length[i]:
		f[v] = max(f[v-length[i]] + length[i], f[v])
		v = v - 1
print max(f[V], sum(length) - f[V]) * 1024 


强烈建议每一种语言有自己的时间时限。Python这个已经不知道还能怎么再优化了。
目前能通过40%。 希望能有人能给出更精简的code
编辑于 2017-04-11 17:30:21 回复(2)
提交观点

问题信息

动态规划
来自：网易2017春招笔试真...
难度：
3条回答 22786浏览

热门推荐

通过挑战的用户

相关试题

双核处理

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号