问题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

来源/分类

二分