【洛谷】P1182 数列分段 Section II

题目描述

对于给定的一个长度为N的正整数数列 A_{1\sim N}A1～N?，现要将其分成 MM（M\leq NM≤N）段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：

例如一数列 4\ 2\ 4\ 5\ 14 2 4 5 1 要分成 33 段。

将其如下分段：

[4\ 2][4\ 5][1][4 2][4 5][1]

第一段和为 66，第 22 段和为 99，第 33 段和为 11，和最大值为 99。

将其如下分段：

[4][2\ 4][5\ 1][4][2 4][5 1]

第一段和为 44，第 22 段和为 66，第 33 段和为 66，和最大值为 66。

并且无论如何分段，最大值不会小于 66。

所以可以得到要将数列 4\ 2\ 4\ 5\ 14 2 4 5 1 要分成 33 段，每段和的最大值最小为 66。

输入格式

第 11 行包含两个正整数 N,MN,M。

第 22 行包含 NN 个空格隔开的非负整数 A_iAi?，含义如题目所述。

输出格式

一个正整数，即每段和最大值最小为多少。

思路：二分答案加贪心，注意的是l与r的取值

ac代码

#include
#include
#include
#include
#include

稍微总结一下，因为这题是求最大值最小，所以用mid+1类板子（查找左边界）

求最小值最大用mid-1版本（查找右边界）