13780 砍树 二分答案

解决思路

 

• 二分查找：使用二分查找来确定伐木机锯片的最大高度 H。

 

• 检查函数：定义一个检查函数 check(mid)，判断在高度 mid 时，能否得到至少 M 米的木材。

 

• 更新边界：根据检查函数的结果，更新二分查找的边界，直到找到最大的 H。

  #include <bits/stdc++.h>
  #define ll long long
  using namespace std;
  const int N = 1e6 + 10;
  ll n, m, a[N];// 检查在高度 mid 时，能否得到至少 m 米的木材
  bool check(ll mid) {ll sum = 0;for (int i = 1; i <= n; i++) {if (a[i] > mid) {sum += a[i] - mid;}}return sum >= m;
  }int main() {// 读取树木的数量和需要的木材总长度cin >> n >> m;ll l = 0, r = 0, ans = 0;// 读取每棵树的高度，并找到最高的树for (int i = 1; i <= n; i++) {cin >> a[i];r = max(r, a[i]);}// 二分查找确定伐木机锯片的最大高度while (l <= r) {ll mid = (l + r) / 2;if (check(mid)) {ans = mid; // 更新答案l = mid + 1; // 尝试更高的高度} else {r = mid - 1; // 尝试更低的高度
          }}// 输出锯片的最高高度cout << ans;return 0;
  }