题目描述（HDU3486）： 姚耀想聘请 m 个人，有 n 个人前来面试。姚耀决定为这项任务选择 m 个面试官。首先，他将面试者按到来的顺序分成 m 段，每段的长度都是 ，这意味着他忽略了来晚的面试者。然后将每段都分配给面试官，面试官从他们中选择最好的一个作为雇员。每个面试者都有一个能力值，能力值越高越好。姚耀希望尽可能减少雇员，且员工的能力值总和大于 k 。请帮他找到最小的 m 。

输入： 输入包含多个测试用例。每个测试用例的第1行都包含两个数字 n 和 k ，表示面试的人数和姚耀想聘用的员工能力值之和（ n ≤200000， k ≤1000000000）；第2行都包含 n 个数字 v 1 , v 2 , …, v n （0≤ v i ≤1000），分别表示每个面试者的能力值。以两个-1结束，不处理。

输出： 对每个测试用例，都单行输出可以找到的最小 m 。若找不到，则输出-1。

提示： 需要3名面试官来帮助姚耀。第1个面试官面试1～3号，第2个面试官面试4～6号，第3个面试官面试7～9号，剩下的人（10～11号）被忽略。每段最大的能力值之和100+101+100=301>300，满足条件。

题解： 本题属于RMQ问题，可用ST解决。假设知道最小的分段数 m ，其 m 个分段的最大值之和必然大于 k 。问题是不知道最小分段数 m ，可以采用二分搜索找到 m 。

1. 算法设计

统计所有输入数据的和值，若该和值小于或等于 k ，则输出-1；否则创建ST；二分搜索找 m ，输出最小值 m 即可。 IS3Xvo0xc3M/J4fna24qkzofDKpO1690AOVGPcHkvk7gfTW1o18x63du1bYjKYUs

2. 算法实现