使用洛谷P1873举例
- 看出这个题目考的是二分答案
- 找出题目横纵坐标,横坐标是我们要输出的东西(也是L和R),纵坐标是输入的m,理解题目,观察横纵坐标的递增递减关系
- 这个题目里面输入的m是所得到的木材,横坐标是锯片的高度,锯片越高得到的木材越少,所以是递减关系
- 开始写二分模板,写check函数,与check函数结果比较的是m,查看题目中有没有给出至少至多这样的字眼,找出来,以小于等于或者大于等于的字眼放到结果与m之间,至少就是小于等于
- 如果题目中没有至少至多,只有==m,那么就找题目中要求的横坐标的多还是少,来找到相同的m,是要左边的还是右边的,例P1182
- 如果题目中没有至少至多,只有==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; }
标签:二分,题目,int,mid,作题,long,心得,check From: https://www.cnblogs.com/jienow/p/17759557.html