![算法训练营:海量图解+竞赛刷题(进阶篇)](https://wfqqreader-1252317822.image.myqcloud.com/cover/239/47379239/b_47379239.jpg)
上QQ阅读APP看本书,新人免费读10天
设备和账号都新为新人
训练3 最小分段数
题目描述(HDU3486):姚耀想聘请m个人,有n个人前来面试。姚耀决定为这项任务选择m个面试官。首先,他将面试者按到来的顺序分成m段,每段的长度都是,这意味着他忽略了来晚的面试者。然后将每段都分配给面试官,面试官从他们中选择最好的一个作为雇员。每个面试者都有一个能力值,能力值越高越好。姚耀希望尽可能减少雇员,且员工的能力值总和大于k。请帮他找到最小的m。
输入:输入包含多个测试用例。每个测试用例的第1行都包含两个数字n和k,表示面试的人数和姚耀想聘用的员工能力值之和(n≤200000,k≤1000000000);第2行都包含n个数字v1, v2, …, vn(0≤vi≤1000),分别表示每个面试者的能力值。以两个-1结束,不处理。
输出:对每个测试用例,都单行输出可以找到的最小m。若找不到,则输出-1。
![](https://epubservercos.yuewen.com/B221B0/26763902601483406/epubprivate/OEBPS/Images/40886-00-52-2.jpg?sign=1739196764-ri3JCDy8pOYFPIKepapdA5nsWWRt0Ufz-0-ebafd8e70d259464b6b7dc3929b47270)
提示:需要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即可。
2. 算法实现
![](https://epubservercos.yuewen.com/B221B0/26763902601483406/epubprivate/OEBPS/Images/40886-00-53-1.jpg?sign=1739196764-pkfMi71UAMlrisqFOT6yudEAxwfePvGi-0-c44c749d8054fd9503a3bca3067a6e87)