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

二分答案学习目标

 先学习单调性，二分查找的单调性意思

二分答案单调性

 二分答案的思路

[【二分答案】-砍树]

#include <iostream>
using namespace std;
int main(){
    int n, m;
    int tree[1000005];
    cin >> n >> m;
    for(int i = 1;i <= n; i++){
        //输入每棵树的高度
        cin >> tree[i];
    }
    int height = 0;
    for(int i = 1;i <= n; i++){
        if(tree[i] > height){
            height = tree[i];
        }
    }
    int left = 0, right = height, mid, ans;
    while(left <= right) {//二分框架
        mid = (left + right) / 2;
        //计算高度mid时能锯的木材
        long long sum = 0;
        for(int j = 1;j <= n; j++){
            if(tree[j] > mid) {
                sum += tree[j] - mid;
            }
        }
        //判断是否达到要求的木材m
        if(sum >= m){
            ans = mid;
            left = mid + 1; 
        } else right = mid - 1; 
    }
    cout << ans;
    return 0;
}