洛谷原题 https://www.luogu.com.cn/problem/P1182
p1182 数列分段
是刚学二分答案的弱鸡
不是因为刷最短路的时候碰到通往奥格瑞玛的道路才来学二分的
是一道非常简单的二分答案(废话)
二分答案, 窝的理解就是二分查找加判定, 一般适用于求最大的最小值或者最小的最大值之类的, 查找答案的区间具有单调性. 就是在涵盖答案的区间里二分搜索, 用一个 judge 函数来判断是否满足答案的要求, 如果恰好是第一个满足要求的就找到了答案.
说说这道题, 其实一开始窝没看懂上哪搜答案 (区间是啥啊) 其实手模一遍样例很简单.
M 是大于 1 小于 N 的, 那么我们至多分成 N 段至少分成 1 段, 在这两个极端下, 前者的最大值必定是这 N 个正整数中最大的 A_i, 后者的最大值就是 N 个数的总和 ($$A_1$$+$A_2$+...+$A_N$), 那么答案一定会是在[$A_i$,($A_1$+$A_2$+...+$A_N$)] 这个区间里!
既然确定区间了, 剩下的就是判定了
先双手捧上代码
- bool judge(int max){/* 判断 max 是否能作为答案 */
- for(int i = 0; i <n; i++){/* 还是 "%ni" 一遍, 会发现其实 tim 记的就是如果要按 max 为答案分, 能分成几组 */
- if(total+a[i]<=max) total += a[i];/* 合起来比 max 小就是一组 */
- else total = a[i],tim++;/* 合起来大了就把之前记下的那堆合成一组 */
- }
- return tim>= m;/* 如果最后分的组多了的话, 那么说明目前的 max 大了, 少了就是小了 */
- }
按照这个返回值, 就是 max 大了返回 0,max 小了返回 1, 那么怎么查找也就很明确了
- while(lef<=rig){
- mid = (lef+rig)/2;
- total = 0, tim = 0;
- if(judge(mid)) lef = mid + 1;/*max 小了就让中间值成为左端点, 右半部分就是我们剩下要搜的区间 */
- else rig = mid - 1;/*max 大了就让中间值成为右端点, 左半部分就是我们剩下要搜的区间 */
- }
那么这个题, 就 AC 了!
全部代码
- #include<bits/stdc++.h>
- using namespace std;
- int n,m,a[100100],lef,rig,mid,total,tim;
- bool judge(int max){
- for(int i = 0; i <n; i++){
- if(total+a[i]<=max) total += a[i];
- else total = a[i],tim++;
- }
- return tim>= m;
- }
- int main(){
- cin>>n>>m;
- for(int i = 0; i <n; i++){
- cin>>a[i];
- rig+=a[i];
- lef = lef> a[i] ? lef: a[i];
- }
- while(lef<=rig){
- mid = (lef+rig)/2;
- total = 0, tim = 0;
- if(judge(mid)) lef = mid + 1;
- else rig = mid - 1;
- }
- cout<<lef;
- return 0;
- }
谢谢!
来源: http://www.bubuko.com/infodetail-3350265.html