C++U4-第06课-二分答案

上节课作业解析

链接：https://pan.baidu.com/s/1QCDg1GXb5HhrpkPgomOCyg?pwd=s4b4
提取码：s4b4

二分答案学习目标

二分查找单调性意思

 二分答案单调性

 二分答案的思路

[【二分答案】砍树(简单版)]

枚举每一棵树，注意当锯片高度高于树的高度时砍的树木是 0。

#include <iostream>
using namespace std;

int a[1000009], n;
long long sum(int x) {
    long long s = 0;
    for (int i = 1; i <= n; i++) {
        s += max(0, a[i] - x);
    }
    return s;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int h;
    cin >> h;
    cout << sum(h);
    return 0;
}

[【二分答案】 砍树]

#include <iostream>
using namespace std;

int a[1000009], n, m; // 定义大小为1000009的整数数组a，变量n和m

// 判断是否满足条件
bool sum(int x) {
    long long s = 0;
    for (int i = 1; i <= n; i++) {
        s += max(0, a[i] - x); // 计算s，累加大于x的元素与x之差
    }
    return s >= m; // 返回是否满足目标值m
}

int main() {
    cin >> n >> m; // 输入n和m

    for (int i = 1; i <= n; i++) {
        cin >> a[i]; // 输入数组a的元素
    }

    int l = 0, r = 1e9, ans; // 初始化左边界l为0，右边界r为1e9（10^9），结果ans

    while (l <= r) {
        int mid = (l + r) >> 1; // 计算中间值mid，等于左右边界之和的一半

        if (sum(mid)) {
            ans = mid; // 如果满足条件，则更新结果ans为当前的mid
            l = mid + 1; // 更新左边界l为mid+1，继续在更大的数段中搜索
        }
        else {
            r = mid - 1; // 否则，更新右边界r为mid-1，继续在更小的数段中搜索
        }
    }

    cout << ans; // 输出结果ans
    return 0;
}

代码的具体思路如下：

声明一个大小为1000009的整数数组 a，以及变量 n 和 m。
定义函数 sum，用于判断是否满足条件。在函数内部，使用循环遍历数组 a，并累加大于 x 的元素与 x 之差，将结果保存在变量 s 中。最后，返回 s 是否大于等于目标值 m。
主函数开始，读取输入的整数 n 和 m，表示数组 a 的长度和目标值。
使用循环读取数组 a 的元素。
初始化左边界 l 为0，右边界 r 为1e9（即10^9），用于确定二分答案的搜索范围。
进行二分查找，当左边界小于等于右边界时，进行循环迭代。
在每次迭代中，计算中间值 mid，使用位运算 (l + r) >> 1 将左右边界之和除以2。
调用 sum(mid) 判断是否满足条件，如果满足，则更新结果 ans 为当前的 mid，并将左边界 l 更新为 mid + 1，继续在更大的数段中搜索。
如果不满足条件，则将右边界 r 更新为 mid - 1，继续在更小的数段中搜索。
当左边界大于右边界时，二分查找结束，得到满足条件的最优解 ans。
输出结果 ans。
返回0表示程序正常结束。
该代码使用二分答案的方法，在给定的范围内查找满足条件的最优解，并输出结果。通过调用 sum 函数来判断是否满足条件，根据返回值更新左右边界进行二分查找。最终得到的 ans 是满足条件的最优解。

[数列分段]

 【数列分段视频讲解，思路一样，代码有一点差别】 https://www.bilibili.com/video/BV1ye4y1D7Xs/?share_source=copy_web&vd_source=a7ac0c0928d95f5dba9f91d92ac06af8

#include <iostream>
using namespace std;

const int maxn = 1e5 + 10; // 定义常量maxn为1e5 + 10
int A[maxn], N, M; // 定义整数数组A，变量N和M

// 判断是否满足条件
bool check(int mid) {
    int section = 0; // 初始化区间个数section为0

    for (int i = 1; i <= N; i++) { // 循环遍历数组A的元素
        int j = i, sum = 0; // 定义变量j为i，sum为0
        section++; // 增加区间个数

        while (j <= N && sum + A[j] <= mid) { // 在当前区间内查找满足条件的子区间
            sum += A[j]; // 累加当前元素到sum
            j++; // 移动指针j
        }

        i = j - 1; // 更新指针i为j-1，跳过已经访问的元素
    }
    
    return section <= M; // 返回区间个数是否小于等于目标值M
}

int main() {
    cin >> N >> M; // 输入N和M

    int ma = 0; // 初始化最大元素ma为0

    for (int i = 1; i <= N; i++) { // 循环读取数组A的元素
        cin >> A[i];
        ma = max(ma, A[i]); // 更新最大元素ma
    }

    int l = ma, r = 1e9, ans; // 初始化左边界l为ma，右边界r为1e9（10^9），结果ans

    while (l <= r) { // 二分查找，当左边界小于等于右边界时进行循环
        int mid = (l + r) >> 1; // 计算中间值mid，等于左右边界之和的一半
        
        if (check(mid)) { // 如果满足条件，则更新右边界r为mid-1，并更新结果ans为当前的mid
            r = mid - 1;
            ans = mid;
        } else { // 否则，更新左边界l为mid+1
            l = mid + 1;
        }
    }

    cout << ans; // 输出结果ans
    return 0;
}

代码的具体思路如下：

声明一个大小为 maxn 的整数数组 A，以及变量 N 和 M。
定义函数 check，用于判断是否满足条件。在函数内部，使用两个指针 i 和 j 遍历数组 A，并同步累加元素到变量 sum 中。每次发现满足条件时，增加区间 section 的个数，并将指针 i 更新为 j-1，跳过已经访问的元素。最后返回区间个数是否小于等于目标值 M。
主函数开始，读取输入的整数 N 和 M，表示数组 A 的长度和目标值。
使用循环读取数组 A 的元素，并更新最大元素 ma。
初始化左边界 l 为 ma，右边界 r 为1e9（即10^9），用于确定二分答案的搜索范围。
进行二分查找，当左边界小于等于右边界时，进行循环迭代。
在每次迭代中，计算中间值 mid，使用位运算 (l + r) >> 1 将左右边界之和除以2。
调用 check(mid) 判断是否满足条件，如果满足，则将右边界 r 更新为 mid - 1，并更新结果 ans

本节课作业视频分享

链接：https://pan.baidu.com/s/1JLX8ZIGJFzoRtGASZIINsw?pwd=qzwj
提取码：qzwj