きこりのミルコは、ある特殊な伐採機を用いて、要求される長さの木材を収集します。この伐採機は、設定された高さ H を基準に動作します。具体的には、伐採機は巨大な鋸刃を高さ H まで持ち上げ、その高さよりも高い部分を持つ全ての木から、H を超える部分を切り落とします。切り落とされた部分がミルコによって収集されます。H 以下の高さの木はそのまま残り、切り落とされることはありません。

例えば、高さがそれぞれ 20, 15, 10, 17 メートルの木々が一列に並んでいるとします。ミルコが鋸刃を 15 メートルの高さに設定した場合、最初の木 (20m) からは 5 メートル (20-15)、4番目の木 (17m) からは 2 メートル (17-15) の木材が得られます。合計で 7 メートルの木材が収集されます。切り落とされた後の木の高さはそれぞれ 15, 15, 10, 15 となります。

ミルコは環境への配慮から、必要以上の木材を伐採することを望んでいません。そのため、彼は可能な限り高い位置で鋸刃を設定したいと考えています。ここで求められるのは、少なくとも M メートルの木材が得られるような、鋸刃の最大の整数高さ H です。もし H をさらに 1 メートル高くすると、M メートルの木材を得られなくなるような、その境界の高さを見つけることが目的です。

問題の定義

N 本の木々の高さが与えられ、合計で M メートル以上の木材が必要な場合、鋸刃の最大切断高さ H を求めます。各木の高さは tree_heights[i] で表されます。

任意の切断高さ H において、収集される木材の総量 collected_wood(H) は、各木 tree_heights[i] について max(0, tree_heights[i] - H) を合計したものです。

鍵となる考察：単調性

切断高さ H と収集される木材の総量 collected_wood(H) の関係を考えると、H の値が増加するにつれて、収集される木材の総量は減少するか、または一定に保たれます。この単調減少性（または非増加性）の性質は、探索問題を効率的に解決するための二分探索（Binary Search）アルゴリズムを適用できることを意味します。

つまり、ある高さ H で必要な木材 M を確保できる場合、それよりも低い高さ H' < H でも確実に M メートル以上の木材を確保できます。逆に、ある高さ H で M メートルに満たない場合、それよりも高い高さ H'' > H ではさらに少ない木材しか得られないため、やはり M メートルを確保することはできません。

二分探索アルゴリズム

この問題の最適な切断高さ H を見つけるために、二分探索を利用します。探索範囲は H が取りうる最小値（0）から最大値（最も高い木の高さ）までです。

1. 探索範囲の初期設定

• low: 可能な最小の切断高さ。通常は 0。
• high: 可能な最大の切断高さ。これは与えられた木々の中で最も高い木の高さです。
• answer: 最終的な結果を格納する変数。初期値は 0。

2. 収集木材計算関数 (calculateCollectedWood)

特定の切断高さ currentHeight が与えられたときに、収集できる木材の総量を計算する関数を定義します。この関数は、与えられた currentHeight で木材が requiredAmount 以上収集できるかどうかを判定し、実際の収集量を返します。

long long getCollectedWoodAmount(int cutLevel, const std::vector<int>& treeHeights) {
    long long currentTotalWood = 0;
    for (int treeHeight : treeHeights) {
        if (treeHeight > cutLevel) {
            currentTotalWood += (long long)(treeHeight - cutLevel);
        }
    }
    return currentTotalWood;
}

3. メインの二分探索ループ

low が high 以下である限り、ループを続けます。

1. 中間値の計算: mid = low + (high - low) / 2 を計算します。これによりオーバーフローを防ぎつつ、探索範囲の中間点を求めます。

2. 木材の収集量判定: getCollectedWoodAmount(mid, treeHeights) を呼び出し、その結果を M と比較します。

   • もし getCollectedWoodAmount(mid, treeHeights) >= M であれば:

     mid は必要な木材を確保できる有効な切断高さです。私たちは最大の H を探しているため、mid を一時的な答え optimalCutHeight として保存し、さらに高い H で試すために探索範囲の下限を mid + 1 に設定します（low = mid + 1）。

   • もし getCollectedWoodAmount(mid, treeHeights) < M であれば:

     mid は高すぎるため、必要な木材を確保できません。より低い H を試すために探索範囲の上限を mid - 1 に設定します（high = mid - 1）。

3. ループが終了したとき、optimalCutHeight には少なくとも M メートルの木材を確保できる最大の切断高さが格納されています。

C++での実装例

以下のコードは、上記の二分探索アルゴリズムをC++で実装したものです。

#include <iostream>
#include <vector>
#include <algorithm> // for std::max_element

// 特定の切断高さで収集できる木材の総量を計算する関数
long long getCollectedWoodAmount(int cutLevel, const std::vector<int>& treeHeights) {
    long long currentTotalWood = 0;
    for (int treeHeight : treeHeights) {
        if (treeHeight > cutLevel) {
            currentTotalWood += (long long)(treeHeight - cutLevel);
        }
    }
    return currentTotalWood;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int numberOfTrees;
    long long minimumRequiredWood; // Mは最大2*10^9なのでlong long
    std::cin >> numberOfTrees >> minimumRequiredWood;

    std::vector<int> heights(numberOfTrees);
    int maxTreeHeight = 0;
    for (int i = 0; i < numberOfTrees; ++i) {
        std::cin >> heights[i];
        if (heights[i] > maxTreeHeight) {
            maxTreeHeight = heights[i];
        }
    }

    int low = 0;
    int high = maxTreeHeight;
    int optimalCutHeight = 0; // 結果を格納する変数

    while (low <= high) {
        int mid = low + (high - low) / 2; // (low + high) / 2 と同じだがオーバーフロー対策
        
        // mid の高さで収集できる木材の量を計算
        if (getCollectedWoodAmount(mid, heights) >= minimumRequiredWood) {
            // mid の高さで必要な木材が確保できる場合、
            // これは有効な答えであり、より高い H を試すことができる
            optimalCutHeight = mid;
            low = mid + 1;
        } else {
            // mid の高さでは必要な木材が確保できない場合、
            // mid は高すぎるので、H を下げる必要がある
            high = mid - 1;
        }
    }

    std::cout >> optimalCutHeight << std::endl;

    return 0;
}