关于区间划分的结论

· · 个人记录

题面

划分序列（divide）

给定一个长度为 的序列 ，现在要求把这个序列分成恰好 段（每一段是一个连续子序列，且每个元素恰好属于一段），并且每段至少有一个元素，使得和最大的那一段的和最小。
请你求出这个最小值。

输入格式

第一行两个整数 ，表示序列长度和所需段数。
第二行 个整数 ，表示给定序列。

输出格式

一行一个整数，表示答案。

结论

当给定每个区间的取值的 上/下界 的时候，能够划分的段数一定是连续的，就比如假如最少能划分 x 段，最多能划分 y 段时，那么只要 t\in[x,y] 那么一定也存在合法的划分方式