喵哈喽~！主人，今天我们来解决一个关于建造水族馆的可爱问题，喵~ 这个问题需要一点点小智慧，但别担心，我会一步一步引导你的！

题目大意

题目是这样子的：你有一个由 n 个珊瑚柱组成的珊瑚礁，第 i 个珊瑚柱的高度是 a_i。然后呢，你要围绕这个珊瑚礁建造一个水箱。

你需要选择一个整数高度 h (h ≥ 1)，然后在珊瑚礁的两边建造高度为 h 的墙壁。

接下来就是最有趣的部分啦——放水！我们会往水箱里注水，直到水面达到 h 的高度。但是有个小规则：如果某个珊瑚柱本身就比 h 高，那它就会露出水面，我们也不需要为它额外加水啦。

比如说，如果珊瑚柱高度是 [3, 1, 2, 4, 6, 2, 5]，我们选择的水箱高度 h=4。那么需要的水量就是： (4-3) + (4-1) + (4-2) + (4-4) + 0 (因为6>4) + (4-2) + 0 (因为5>4) = 1 + 3 + 2 + 0 + 0 + 2 + 0 = 8 个单位的水，喵~

问题来啦：你最多只能用 x 单位的水。那么，在不超过用水限制的情况下，你能建造的水箱最大高度 h 是多少呢？

---

题解方法

这个问题看起来有点棘手，但其实只要找到其中的小秘密，就迎刃而解啦，喵~

我们来观察一下水箱高度 h 和所需水量 w 之间的关系。随着我们把 h 选得越来越大，需要填满的水量 w 是不是也单调递增的呀？（或者至少不会减少）

比如说，h 从 4 增加到 5，每一根比 5 矮的珊瑚柱都需要更多的水，总水量肯定会增加。这种“一个变大，另一个也跟着变大”的性质，我们称之为单调性。

一看到单调性，我们聪明的脑袋里就应该亮起一盏灯：二分查找！

没错，我们可以对答案 h 进行二分查找！因为如果一个高度 h 是可行的（水够用），那么所有比 h 小的高度也一定是可行的。反之，如果一个高度 h 不可行（水不够），那么所有比 h 大的高度也一定不可行。这完美符合二分查找的应用场景。

具体怎么做呢？

1. 确定 h 的范围：

   • 下界 (low)：题目说了 h ≥ 1，所以下界就是 1。
   • 上界 (high)：我们需要一个足够大的数。可以想一下，h 最大能到多少？即使把所有的水 x (最多 10^9) 都加到一根高度为 1 的珊瑚柱上，高度也才 1 + 10^9。考虑到 a_i 最大也是 10^9，一个 2*10^9 左右的数就足够了。为了保险和方便，我们可以直接取一个更大的数，比如 3*10^9，这样肯定就够用了，喵~

2. 写一个 check 函数： 这个函数用来判断，对于一个给定的高度 mid，我们是否能用不超过 x 的水来建造。计算方法很简单：遍历所有珊瑚柱 a_i，如果 mid > a_i，我们就需要 mid - a_i 的水量。把所有需要的水量加起来，和 x 比较一下就好啦。

3. 开始二分： 我们在 [low, high] 的范围内寻找答案。

   • 取中间值 mid = low + (high - low) / 2。
   • 调用 check(mid)：
     • 如果返回 true，说明高度 mid 是可行的（水够用！）。既然可行，我们是不是可以贪心一点，试试更高的高度呢？所以，我们把 mid 记作一个可能的答案，然后去右半边区间 [mid + 1, high] 继续寻找，看看有没有更好的解，喵~
     • 如果返回 false，说明高度 mid 太高了，水不够用啦！那我们只能降低要求，去左半边区间 [low, mid - 1] 寻找一个矮一点的可行高度。

就这样一直循环，直到 low > high，我们最后记录的那个可行的答案，就是最大的 h 啦！

---

题解

好啦，理论说完了，我们来看看代码是怎么用爪子把这个想法敲出来的吧，喵~

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

void solve() {
    long long n;
    long long x;
    std::cin >> n >> x;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 我们在寻找最大的可行高度 'h'。
    // 所需水量是 'h' 的一个非递减函数。
    // 这种单调性允许我们对答案 'h' 进行二分查找。

    // 'h' 的下界是 1，根据题目要求。
    long long low = 1;
    // 'h' 的一个安全的上界。最大可能的高度可以估算。
    // 如果 h > max(a_i) + x，那么至少有一根柱子所需的水量会超过 x。
    // max(a_i) <= 10^9, x <= 10^9。所以 h <= 2*10^9。
    // 一个宽松的上界如 3*10^9 既安全又简单。
    long long high = 3000000000LL;
    long long ans = 0;

    // Lambda 函数，用于检查给定的高度 'h' 是否可行。
    // 它通过引用捕获 'x' 和 'a' 以避免复制。
    auto is_possible = [&](long long h) {
        long long water_needed = 0;
        for (int val : a) {
            if (h > val) {
                water_needed += (h - val);
            }
            // 优化：如果所需水量已超过预算，则无需继续。
            if (water_needed > x) {
                return false;
            }
        }
        return true;
    };

    while (low <= high) {
        long long mid = low + (high - low) / 2;
        
        if (is_possible(mid)) {
            // 如果高度 'mid' 可行，它就是我们答案的一个候选。
            // 我们尝试寻找一个更大的可行高度。
            ans = mid;
            low = mid + 1;
        } else {
            // 如果高度 'mid' 不可行，说明它太高了。
            // 我们必须在更低的范围里搜索。
            high = mid - 1;
        }
    }
    std::cout << ans << std::endl;
}

int main() {
    // 竞赛编程中的快速 I/O
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

代码解说

1. solve() 函数：每个测试用例都会调用这个函数。
2. 读入数据：long long n, x; 和 std::vector<int> a(n); 用来存储珊瑚柱数量、最大水量和各个珊瑚柱的高度。
3. 设定二分边界：long long low = 1; 和 long long high = 3000000000LL;。就像我们刚才讨论的，low 是题目要求的最小高度，high 是一个足够大的上界，保证答案一定在它之下。ans 用来记录我们找到的可行答案。
4. is_possible lambda 函数：这就是我们的 check 函数！它用 [&] 捕获了外部的 x 和 a，这样就不用传来传去了，很方便的说。
   • 函数内部，water_needed 初始化为0。
   • 遍历所有珊瑚柱 val，如果 h > val，就把差值 h - val 加到 water_needed 上。
   • 这里还有一个小优化哦：如果在计算过程中 water_needed 已经超过 x 了，那就没必要再算下去了，直接返回 false，告诉外面这个 h 太高了，喵~
   • 如果循环结束 water_needed 还没超过 x，就返回 true。
5. 二分循环 while (low <= high)：
   • mid = low + (high - low) / 2; 这是标准的计算中间值的方法，可以防止 low + high 溢出哦。
   • if (is_possible(mid))：如果 mid 可行，我们就更新 ans = mid;，然后 low = mid + 1; 去尝试更大的高度。
   • else：如果 mid 不可行，就 high = mid - 1; 去尝试更小的高度。
6. 输出结果：循环结束后，ans 中存储的就是我们能找到的最大的可行高度 h，把它打印出来就好啦！

---

知识点介绍

最后，我们来总结一下这个题目里用到的超有用的知识点吧，喵~

二分查找 (Binary Search)

二分查找是一种在有序数据集里查找特定元素的算法。它的核心思想是每次都将搜索范围缩小一半。想象一下在字典里查单词，你不会一页一页翻，而是直接翻到中间，看要找的单词在前半部分还是后半部分，然后对那一半再重复这个过程。这就是二分查找！

它的时间复杂度是 O(log N)，非常非常快，是解决很多问题的利器哦！

答案二分 (Binary Search on the Answer)

这是一个二分查找的绝妙应用！有时候，问题本身不是让你在数组里找东西，而是让你找一个满足特定条件的最优值（比如最大值、最小值）。

如果这个“特定条件”对于答案来说具有单调性，我们就可以用二分来“猜”答案。

就拿这道题来说：

• 条件: 高度为 h 时，所需水量不超过 x。
• 单调性: 如果高度 h 满足条件，那么所有比 h 小的高度 h' 也一定满足条件（因为 h' 需要的水更少）。

这种“可行/不可行”的边界清晰的特性，使得我们可以通过二分法快速地逼近这个边界，也就是我们想要的那个最优解 h。这种技巧在竞赛中超级常见，一定要掌握呀，主人！喵~