1417 : 数列划分
时间限制Time Limit
1
秒Sec
内存限制Memory Limit
128
兆MB
提交次数Submitted
183 次Times
通过次数Solved
36 次Times
标准评测 Standard
从标准输入读入,结果写到标准输出。评测将输出拆成 token,与标准答案逐项比较,不按整段逐字节比对。
Read from standard input and write to standard output. The judge splits the output into tokens and compares them with the official answer; it does not compare raw bytes.
| 比对Compare | token 相同即通过。中间的空格、制表符、换行可多可少。Matching tokens pass. Extra spaces, tabs, or newlines between them are ignored. |
|---|---|
| 不同则错Differs | token 个数或内容不同即错误。23 与 2 3、02 与 2、2.0 与 2 均视为不同。A different token count or value is wrong. 23 vs 2 3, 02 vs 2, and 2.0 vs 2 all differ. |
| 输入Input | 标准输入,格式见题面。Standard input; format as in the statement. |
| 输出Output | 标准输出。Standard output. |
题目描述Description
给一个有 \(n\) 个正整数的序列,连续地将其分为互不重叠的 \(k\) 份,即每一份都是该序列的一个子串,不能调换顺序。
求一个划分方案,使数字之和最大的那一份,其和在所有划分方案里最小。
输入格式Input
每组数据第一行两个整数 \(n, k\),其中\(1\leq k \leq n \leq 10^5\)。
第二行 \(n\) 个不大于 \(1000\) 的正整数。
输出格式Output
求划分 \(k\)
份让数字之和最大那一份的和最小的方案,在划分位置标注
“/”,与数字用空格隔开。
如果有多种方案,输出第一个块最小的方案,如果依然多种,则第二个块最小,依此类推。
样例Sample
出题Author
CSGrandeur