jimore

用户名：uq_30465888842

访问量：9720

签　名：

Don't let the dream just be a dream!!!

等　　级
排　　名	176
经　　验	6840
参赛次数	29
文章发表	63
年　　龄	0
在职情况	学生
学　　校	四川农业大学
专　　业	计算机科学与技术

　　自我简介：

目标院校：上海交通大学

TA的其他文章

二分答案（简单理解）
浏览：446

求一个很大的数的所有质因子（新方法）
浏览：246

佩尔方程——模板题
浏览：220

你可能喜欢

A+B for Input-Output Practice (VII) （C语言代码）

优质题解

二分答案（简单理解）

　　作者: jimore　　　　发表时间：2022-07-21 11:42:12 浏览：446　|　评论：1　

原题链接：信息学奥赛一本通T1436-数列分段II

# 二分解法

**以后看到这种将原问题分解成许多子问题，求解子问题的最(大/小)值，就可以用二分答案法，二分最(大/小)值，判断是否满足题目**

就像这个问题，要将一个数组分成 k 段，求最大子段和的最小值，就符合这类问题，类似的还有[875. 爱吃香蕉的珂珂 - 力扣（LeetCode）](https://leetcode.cn/problems/koko-eating-bananas/),[Loading Question... - 力扣（LeetCode）](https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/)等题目

#### 求解步骤

1.定义判断当前答案是否满足题目要求的判断函数 bool isok(int ans)
    bool isok(int ans){
        // 
    }
    2.二分枚举当前答案
    int l,r,mid,ans; // l,r的值视题目而定
    while(l<=r){
        mid=(l+r)/2;
        if(isok(mid))
            ans=mid,l=mid+1;
        else
            r=mid-1;
    }

对于不同题目来说，唯一要改动的就是判断函数`isok(int ans)`

###### 1.判断函数`isok(int ans)`

在这个题目，对于当前枚举到的答案如何判断是否正确呢？

在判断之前，首先要理解 ans 是代表什么， ans 代表当前最大分段的值，也就是说每一个分段的和都不能超过 ans 。所以只需准备一些容量为 ans 的桶，从数组的左边开始按顺序装，直到装到装不下，就换一个桶来装，装完数组所有数之后，数一下桶的数量是否小于等于 m 即题目给的分段限制，如果满足，则返回 true ，否则返回 false 。

bool isok(int sum){
        int sumNum=0; // 统计桶的数量
        int subSum=0; // 统计当前的桶已经装的数量
        int pos=0;  // 数组指针
        while(pos<n){
            if(subSum+a[pos]>sum){
                sumNum++;
                subSum=0;
            }else{
                subSum+=a[pos];
                pos++;
            }
        }
        sumNum++;
        return sumNum<=c;
    }

###### 2.二分枚举

* 首先设置左右指针 l 和 r ，经过分析题目，将 l 赋值为数组的最大值，将 r 赋值为数组的和，大家可以思考一下为什么。
  
* 然后套二分的模板

int l=maxNum,r=totalNum,mid,ans;
    while(l<=r){
        mid=(l+r)/2;
        if(isok(mid))
            ans=mid,r=mid-1;
        else
            l=mid+1;
    }
    cout<<ans<<endl;

#### 完整代码

#include <bits/stdc++.h>
    using namespace std;
    int n,c;
    vector<int>a;
    bool isok(int sum){
        int sumNum=0,subSum=0,pos=0;
        while(pos<n){
            if(subSum+a[pos]>sum){
                sumNum++;
                subSum=0;
            }else{
                subSum+=a[pos];
                pos++;
            }
        }
        sumNum++;
        return sumNum<=c;
    }
    int main(){
        cin>>n>>c;
        int num,maxNum=0,totalNum=0;
        for(int i=0;i<n;i++){
            cin>>num;
            a.push_back(num);
            maxNum=max(maxNum,num);
            totalNum+=num;
        }
        int l=maxNum,r=totalNum,mid,ans;
        while(l<=r){
            mid=(l+r)/2;
            if(isok(mid))
                ans=mid,r=mid-1;
            else
                l=mid+1;
        }
        cout<<ans<<endl;
        // system("pause");
        return 0;
    }

0.0分

10 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

SinzoL

这方法太棒了·！！！

2022-07-29 21:23:41

jimore

TA的其他文章

你可能喜欢

C二级辅导-进制转换（C语言代码）

分糖果（C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言训练-尼科彻斯定理（C++代码）

A+B for Input-Output Practice (VII) （C语言代码）

二分答案（简单理解）

评论区

精彩推荐

分糖果（C++代码）

十->二进制转换（C++代码）（零和负数需要特殊处理）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言训练-斐波纳契数列（C语言代码）

时间转换（Java代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

求圆的面积（C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

jimore

TA的其他文章

你可能喜欢

C二级辅导-进制转换 （C语言代码）

分糖果 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言训练-尼科彻斯定理 （C++代码）

A+B for Input-Output Practice (VII) （C语言代码）

二分答案（简单理解）

评论区

精彩推荐

分糖果 （C++代码）

十->二进制转换 （C++代码）（零和负数需要特殊处理）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言训练-斐波纳契数列 （C语言代码）

时间转换 （Java代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

求圆的面积 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C二级辅导-进制转换（C语言代码）

分糖果（C语言代码）

C语言训练-尼科彻斯定理（C++代码）

　　评论区

分糖果（C++代码）

十->二进制转换（C++代码）（零和负数需要特殊处理）

C语言训练-斐波纳契数列（C语言代码）

时间转换（Java代码）

求圆的面积（C语言代码）