首页 > 试题广场 >

画匠问题

[编程题]画匠问题
  • 热度指数：1162 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个整型数组arr, 数组中的每个值都为正数，表示完成一幅画作需要的时间，再给定一个整数num，表示画匠的数量，每个画匠只能画连在一起(即数组内连续的一段)的画作。所有画家并行工作，请返回完成所有的画作的最少时间。
[要求]
时间复杂度为(其中S表示所有画作所需时间的和)

输入描述:
第一行两个整数N, K表示数组大小，画匠的数量。
接下来一行N个整数表示完成每幅画作所需要的时间。


输出描述:
输出一个整数表示答案
示例1

输入

3 2
3 1 4

输出

4

说明

最好的分配方式为第一个画匠画3和1，所需时间为4，第二个画匠画4，所需时间为4。因为并行工作，所以最少时间为4，如果分配方式为第一个画匠画3，所需时间为3，第二个画匠画1和4，所需的时间为5，那么最少时间为5，显然没有第一种分配方式好，所以返回4
示例2

输入

5 3
1 1 1 4 3

输出

4

说明

最好的分配方式为第一个画匠画前三个1，所需时间为3，第二个画匠画4，所需时间为4，第三个画匠画3，所需时间为3，返回4
示例3

输入

5 2
99 82 44 35 3

输出

164

说明

[99] [82 44 35 3]

备注:

算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

贪心 堆
上传者：小小
难度：
0条回答 3925浏览

热门推荐

通过挑战的用户

查看代码

相关试题

画匠问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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