funpinpin建站平台,网站忧化教程,最火的网络推广平台,河南做网站的公司有哪些二分模板一共有两个#xff0c;分别适用于不同情况。 算法思路#xff1a;假设目标值在闭区间[l, r]中#xff0c; 每次将区间长度缩小一半#xff0c;当l r时#xff0c;我们就找到了目标值。
版本一
当我们将区间[l, r]划分成[l, mid]和[mid 1, r]时#xff0c;其更…二分模板一共有两个分别适用于不同情况。 算法思路假设目标值在闭区间[l, r]中 每次将区间长度缩小一半当l r时我们就找到了目标值。
版本一
当我们将区间[l, r]划分成[l, mid]和[mid 1, r]时其更新操作是r mid或者l mid 1;计算mid时不需要加1。
int bsearch_1(int l, int r)
{while (l r){int mid l r 1;if (check(mid)) r mid;else l mid 1;}return l;
}版本二
当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时其更新操作是r mid - 1或者l mid;此时为了防止死循环计算mid时需要加1。
int bsearch_2(int l, int r)
{while (l r){int mid l r 1 1;if (check(mid)) l mid;else r mid - 1;}return l;
}总结
假设有一个总区间经由我们的 check 函数判断后可分成两部分 这边以o作 true…作 false 示意较好识别
如果我们的目标是下面这个v那麽就必须使用模板 1
…vooooooooo
假设经由 check 划分后整个区间的属性与目标v如下则我们必须使用模板 2
oooooooov…
所以下次可以观察 check 属性再与模板1 or 2 互相搭配就不会写错啦
练习题
503. 借教室
#include iostream
#include cstring
#include algorithmusing namespace std;typedef long long LL;
const int N 1000010;
int n, m;
int w[N];
int d[N], l[N], r[N];
LL b[N];bool check(int mid)
{memset(b, 0, sizeof b);for (int i 1; i mid; i ) {b[l[i]] d[i];b[r[i] 1] - d[i];}for (int i 1; i n; i ) {b[i] b[i - 1];if (b[i] w[i]) return false;}return true;
}int main()
{scanf(%d%d, n, m);for (int i 1; i n; i ) scanf(%d, w[i]);for (int i 1; i m; i ) scanf(%d%d%d, d[i], l[i], r[i]);int l 0, r m;while(l r){int mid l r 1 1;if (check(mid)) l mid;else r mid - 1;}if (r m) printf(0\n);else printf(-1\n%d, r 1);return 0;
}作者大四萌新.
链接https://www.acwing.com/activity/content/code/content/7899026/
来源AcWing
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。1227. 分巧克力
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 1e5 10;int n, k;
int h[N], w[N];bool check(int mid)
{int sum 0;for (int i 0; i n; i ) {sum (h[i] / mid) * (w[i] / mid);if (sum k) return true;}return false;
}int bsearch()
{int l 1, r 1e5 10;while (l r) {int mid l r 1 1;if (check(mid)) l mid;else r mid - 1;}
}int main()
{scanf(%d%d, n, k);for (int i 0; i n; i ) scanf(%d%d, h[i], w[i]);printf(%d, bsearch());return 0;
}作者大四萌新.
链接https://www.acwing.com/activity/content/code/content/7878482/
来源AcWing
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。4956. 冶炼金属
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 10010;
int n;
int a[N], b[N];bool check_1(int mid)
{// 找最小的 那么其他部分都得满足小于等于b[i]for (int i 0; i n; i ) if (a[i] / mid b[i]) return false;return true;
}bool check_2(int mid)
{// 找最大得 那么其他部分都得满足大于等于b[i]for (int i 0; i n; i ) if (a[i] / mid b[i]) return false;return true;
}int main()
{scanf(%d, n);for (int i 0; i n; i ) scanf(%d%d, a[i], b[i]);int l 1, r 1e9 1;while (l r) {int mid l r 1;if (check_1(mid)) r mid;else l mid 1;}printf(%d , l);r 1e9 1;while (l r){int mid l r 1 1;if (check_2(mid)) l mid;else r mid - 1;}printf(%d, l);return 0;
}作者大四萌新.
链接https://www.acwing.com/activity/content/code/content/7899986/
来源AcWing
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
