问题1233--工作分配

1233: 工作分配

时间限制: 1 Sec  内存限制: 128 MB
提交: 105  解决: 28
[提交] [状态] [讨论版] [命题人:]

题目描述

longpo最近很忙，幸好他有很多得力的学生帮他分担工作。现在有n个工作，需要分配给m (m<=n)个人。longpo有一张工作表，a1, a2, … , an分别代表了这n个工作完成所需要的时间。为了方便，longpo给m个学生分配工作时，将连续一段ai—aj (1<= i <= j<= n)工作分配给每个人，每个学生都至少分到一个工作。工作的完成时间，由最晚完成的工作决定的，如有5个工作，每个工作完成的时间分别需要100, 100, 100, 100, 100，现在有4个同学做，那么可以如下分配：
100 / 100 / 100 / 100 100
前三个学生需要100的时间完成，第四个学生需要200的时间完成，那么全部工作完成的时间就是200。longpo希望完成工作的时间越少越少，那么由你帮忙给longpo决策，怎样分配工作。

输入

首先输入n, m
然后输入n个工作所需要的时间

输出

使用”/”将n个工作时间划分成m份，使得总的工作时间最少。方案有多种时，优先保证第一个人分配的工作最少，其次第二个人分配的工作最少……以此类推。
具体格式见样例。

样例输入 Copy 

9 3
100 200 300 400 500 600 700 800 900

样例输出 Copy 

100 200 300 400 500 / 600 700 / 800 900

提示

样例2
5 4
100 100 100 100 100
样例2
100 / 100 / 100 / 100 100
对于30%的数据 1<=m<=n<=30, 1<=ai<=10^3
对于60%的数据1<=m<=n<=100, 1<=ai<=10^5
对于100%的数据1<=m<=n<=500, 1<=ai<=10^8

来源/分类

二分 
[提交] [状态]