P1873 [COCI 2011/2012 #5] EKO / 砍树

例题

• 二分答案
• 解题的时候往往会考虑枚举答案然后检验枚举的值是否正确。若满足单调性，则满足使用二分法的条件。把这里的枚举换成二分，就变成了「二分答案」
• 暴力1到1e9枚举答案 会TLE，在1到1e9区间上进行二分作为答案

#include <bits/stdc++.h>
#define endl '\n'
#define int long long 
#define INF 0x3f3f3f3f3f
const int N = 1000010;
using namespace std;
int a[N];
int n, m;
//return true :mid值小 需要网上调调
//return false:mid值大 需要往下调调 要不不够sum
bool check(int k) {  // 检查可行性，k 为锯片高度
  int sum = 0;
  for (int i = 1; i <= n; i++)       
    if (a[i] > k)                  
      sum += (a[i] - k); 
  return sum >= m;                 
}

int find() {
  int l = 1, r = 1e9 + 1;   // 因为是左闭右开的，所以 10^9 要加 1
  while (l + 1 < r) {       
    int mid = (l + r) / 2;  
    if (check(mid))         
      l = mid;              // 升高锯片高度
    else
      r = mid;  // 否则降低锯片高度
  }
  return l;  // 返回左边值
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  cout << find();
  return 0;
}