二分答案作题心得-526互联

使用洛谷P1873举例

看出这个题目考的是二分答案
找出题目横纵坐标，横坐标是我们要输出的东西(也是L和R)，纵坐标是输入的m，理解题目，观察横纵坐标的递增递减关系
1. 这个题目里面输入的m是所得到的木材，横坐标是锯片的高度，锯片越高得到的木材越少，所以是递减关系
开始写二分模板，写check函数，与check函数结果比较的是m，查看题目中有没有给出至少至多这样的字眼，找出来，以小于等于或者大于等于的字眼放到结果与m之间，至少就是小于等于
1. 如果题目中没有至少至多，只有==m，那么就找题目中要求的横坐标的多还是少，来找到相同的m，是要左边的还是右边的，例P1182

输出 l

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], n, m;
long long check(int high){
  long long all = 0;
  for (int i = 0; i < n; ++i) {
    if (a[i] > high) all += a[i] - high;
  }
  return all;
}
int main(){
  ios::sync_with_stdio(0);
  cin >> n >> m;
  int l = 0, r = 0;
  for (int i = 0; i < n; ++i){
    cin >> a[i];
    r = max(r, a[i]);
  }
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (check(mid) >= m) l = mid;
    else r = mid - 1;
  }
  cout << l << endl;
  return 0;
}