码蹄集 伐木工小码哥

题目来源：码蹄集

题目描述：

B站老师思路讲解链接：https://www.bilibili.com/video/BV1ex4y1P7HJ/?t=875.4&vd_source=3ae2a916df1bc5c1114c2bf3e95a2118

C++代码实现：

参考链接：https://blog.51cto.com/u_15745546/5950627

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

LL n,m;
LL a[1000010];

//判断h是否满足要求
bool check(int h)
{
    LL sum=0;
    for(LL i=0;i<n;i++)
    {
        if(a[i]>h) sum+=(a[i]-h);
    }
    if(sum>=m) return true;
    else return false;
}

int main()
{
    cin>>n>>m;
    
    //求出树的高度最大值作为二分的右端点
    LL r=0;
    for(LL i=0;i<n;i++) 
    {
        scanf("%lld",&a[i]);
        r=max(r,a[i]);
    }
    
    LL l=0;
    while(l<r) //二分板子
    {
        LL mid=l+r+1>>1;

        if(check(mid)) l=mid;
        else r=mid-1;
    }
    
    cout<<l<<endl;
    
    return 0;
}

Python代码实现：

import sys

n, m = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))

r = max(a)

def check(h):
    sum = 0
    for i in range(n):
        if a[i] > h:
            sum += (a[i] - h)
    return sum >= m

l = 0
while l < r:
    mid = (l + r + 1) // 2
    if check(mid):
        l = mid
    else:
        r = mid - 1

print(l)

Java代码实现：

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long m = sc.nextLong();
        long[] a = new long[n];

        long r = 0;
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
            r = Math.max(r, a[i]);
        }

        long l = 0;
        while (l < r) {
            long mid = (l + r + 1) / 2;

            if (check(a, mid, m)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }

        System.out.println(l);
    }

    public static boolean check(long[] a, long h, long m) {
        long sum = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i] > h) {
                sum += (a[i] - h);
            }
        }
        return sum >= m;
    }
}

代码提交测试结果：