题面描述

小明有 $n$ 块木板，第 $i$ 块木板的长度为 $a_i$。他购买了一块长度为 $m$ 的木料，这块木料可以切割成任意长度的块，拼接到已有的木板上，以增加木板的长度。小明希望在增加木板长度后，使得所有木板中最短的那块尽可能长。请问，小明在加长木板后，最短木板的长度最大可以是多少？

思路

为了使所有木板中的最短木板尽可能长，我们需要找到一个最大值 $L$，使得将所有长度小于 $L$ 的木板增加到至少 $L$，所需的总增加长度不超过 $m$。

具体步骤如下：

1. 二分查找：使用二分查找在可能的 $L$ 范围内查找最大可能的最短长度。

   • 左边界：当前木板中的最小长度 min_a。
   • 右边界：当前木板中的最大长度 max_a 加上可用木料 m，即 max_a + m。

2. 验证函数：对于给定的中间值 $L$，计算将所有长度小于 $L$ 的木板增加到 $L$ 所需的总木料量。如果总需求小于或等于 $m$，则 $L$ 是可行的，尝试更大的 $L$；否则，尝试更小的 $L$。

3. 迭代：不断调整二分查找的范围，直到找到最大可能的 $L$。

cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    long long m;
    cin >> n >> m;
    vector<long long> a(n);
    for(auto &x : a) cin >> x;
    
    // 找到当前最小和最大长度
    long long min_a = *min_element(a.begin(), a.end());
    long long max_a = *max_element(a.begin(), a.end());
    
    // 二分查找的左右边界
    long long left = min_a;
    long long right = max_a + m;
    long long answer = min_a;
    
    while(left <= right){
        long long mid = left + (right - left) / 2;
        long long required = 0;
        for(auto x : a){
            if(x < mid){
                required += (mid - x);
                // 如果需求超过m，提前终止
                if(required > m) break;
            }
        }
        if(required <= m){
            answer = mid; // 更新答案
            left = mid + 1; // 尝试更大的mid
        }
        else{
            right = mid - 1; // 尝试更小的mid
        }
    }
    cout << answer;
    return 0;
}

python

def main():
    import sys
    n, m = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))
    
    min_a = min(a)
    max_a = max(a)
    
    left = min_a
    right = max_a + m
    answer = min_a
    
    while left <= right:
        mid = (left + right) // 2
        required = sum((mid - x) for x in a if x < mid)
        if required <= m:
            answer = mid
            left = mid + 1
        else:
            right = mid -1
    print(answer)

if __name__ == "__main__":
    main()

java

import java.util.*;
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 min_a = Long.MAX_VALUE, max_a = Long.MIN_VALUE;
        for(int i=0;i<n;i++){
            a[i] = sc.nextLong();
            if(a[i] < min_a) min_a = a[i];
            if(a[i] > max_a) max_a = a[i];
        }
        long left = min_a;
        long right = max_a + m;
        long answer = min_a;
        while(left <= right){
            long mid = left + (right - left) / 2;
            long required = 0;
            for(int i=0;i<n;i++){
                if(a[i] < mid){
                    required += (mid - a[i]);
                    if(required > m) break;
                }
            }
            if(required <= m){
                answer = mid;
                left = mid + 1;
            }
            else{
                right = mid -1;
            }
        }
        System.out.println(answer);
    }
}

题目内容

小明有 $n$ 块木板，第 $i ( 1 ≤ i ≤ n )$ 块木板长度为 $a_i$。

小明买了一块长度为 $m$ 的木料，这块木料可以切割成任意块，拼接到已有的木板上，用来加长木板。

小明想让最短的模板尽量长。请问小明加长木板后，最短木板的长度可以为多少？

输入描述

输入的第一行包含两个正整数， $n ( 1 ≤ n ≤ 10^3 )$, $m ( 1 ≤ m ≤ 10^6 )$，$n$ 表示木板数， $m$ 表示木板长度。

输入的第二行包含 $n$ 个正整数， $a_1, a_2,…,a_n ( 1 ≤ ai ≤ 10^6 )$。

输出描述

输出的唯一一行包含一个正整数，表示加长木板后，最短木板的长度最大可以为多少？

样例1

输入

5 3
4 5 3 5 5

输出

5

说明

给第 $1$ 块木板长度增加 $1$ ，给第 $3$ 块木板长度增加 $2$后，

这 $5$ 块木板长度变为 $[5,5,5,5,5]$ ，最短的木板的长度最大为 $5$ 。

样例2

输入

5 2
4 5 3 5 5

输出

4

说明

给第 $3$ 块木板长度增加 $1$ 后，这 $5$ 块木板长度变为 $[4,5,4,5,5]$ ，剩余木料的长度为 $1$ 。此时剩余木料无论给哪块木板加长，最短木料的长度都为 $4$ 。