在 A 题里面，pwp 给出一些手写二分的代码喵，例如：

int a[100005], n, x;

int L = 1, R = n + 1;
while (L < R)
{
    int mid = L + R >> 1;
    if (a[mid] < x)
        L = mid + 1;
    else //a[mid] >= x
        R = mid;
}

对于这段代码，把 if 判定内的条件表达式提取出来，阔以变成这样子 qwq：

int a[100005], n, x;

int L = 1, R = n + 1;
while (L < R)
{
    int mid = L + R >> 1;
    if (check(mid)) //a[mid] < x
        L = mid + 1;
    else //a[mid] >= x
        R = mid;
}

其中，check 函数就对应的是

bool check(int mid)
{
    return a[mid] < x;
}

那喵，提取这个 check 函数做什喵？pwp

这已经很明显了喵，pwp 要说到二分答案了喵，不许打断喵。

二分答案，其实就是在满足单调性的可能答案的值域上二分找到那个最恰好的答案喵。二分答案仍然阔以当成一种二分查找，不过被查的数组 a 有 a_i = i，且数组的长度 |a| 阔以达到 10^9 大小；另外二分答案的 check 函数也常常更加复杂，一次 check 的时间复杂度也一般会达到 O(n)。

叽里咕噜说什么呢

这种破概念肯定不会有笨蛋想死磕叭 qwq，当然是直接用实际题目来理解会比较好啦(

给定一个长度为 n 的数组 a，需要把数组分成 k 个连续的段，分完后这 k 段段内元素之和的最大值最小是多少？本题使用多测 qwq。

第一行一个整数 T(1 \le T \le 10^5)，表示多测的测试用例数。

对于每个测试用例，其第一行输入两个整数 n, k(1 \le k \le n \le 10^5)，表示数组长度和需要分的段数；第二行输入 n 个整数表示数组 a(1 \le i \le n, 1 \le a_i \le 10^9)。

数据保证 \sum{n} \le 10^5。

对于每个测试用例，输出一行一个整数表示答案。

提示？pwp

很明显了喵 qwq

按照二分答案的说法，二分这个最小的最大段内和 x，然后 check 的时候贪心地把每一段拉满，看这样分的段数会不会超过 k 就行喵 qwq。