本文主要是介绍蓝桥杯备赛之二分专题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
常用的算法二分模板
1. 在数组a[]中找大于等于x的第一个数的下标
//int ans = lower_bound(a, a + n, x) - a
//相当于下方
int l = 0, r = n - 1;
while(l < r) {int mid = l + r >> 1;if(a[mid] >= x) r = mid;else l = mid + 1;
}
cout << r;
2. 在数组a[]中找大于x的第一个数的下标
//int ans = upper_bound(a, a + n, x) - a
//相当于下方
int l = 0, r = n - 1;
while(l < r) {int mid = l + r + 1 >> 1;if(a[mid] <= x) l = mid;else r = mid + 1;
}
cout << r;
例题
503.借教室
题目
思路
代码
//根据题意：有单调性，区间操作 二分+差分
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int r[N], d[N], s[N], t[N];
LL b[N]; //差分数组
int n, m;
bool check(int mid) {for(int i = 1; i <= n; i++) b[i] = r[i] - r[i - 1]; //初始化差分数组for(int i = 1; i <= mid; i++) {b[s[i]] -= d[i];b[t[i] + 1] += d[i];}for(int i = 1; i <= n; i++ ) {b[i] += b[i - 1];if(b[i] < 0) return true;}return false;
}
int main() {scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) scanf("%d", &r[i]);for(int i = 1; i <= m; i++) scanf("%d%d%d", &d[i], &s[i], &t[i]);int l = 1, r = m;if(!check(m)) {puts("0");return 0;}while(l < r) {int mid = l + r >> 1;if(check(mid)) r = mid;else l = mid + 1;}printf("-1\n%d", r);return 0;
}
5407.管道
题目
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
typedef long long LL;
int n, len;
int l[N], s[N];
pair<int, int> q[N];
bool check(LL mid) { //mid为当前时间int cnt = 0;for(int i = 1; i <= n; i++) {if(s[i] <= mid) {// q[cnt++] = {mid - s[i], mid + s[i]}; 别忘了区间长度限制int d = mid - s[i];LL L = max(1, l[i] - d), R = min((LL)len, (LL)l[i] + d);q[cnt++] = {L, R};}}sort(q, q + cnt);int st = -1, ed = -1;for(int i = 0; i < cnt; i++) {//这里是 ed+1 因为需要的是每个节点有水，相当于“相连”if(q[i].first <= ed + 1) ed = max(ed, q[i].second);else {st = q[i].first, ed = q[i].second;}}return st == 1 && ed == len;
}
int main() {scanf("%d%d", &n, &len);for(int i = 1; i <= n; i++)scanf("%d%d", &l[i], &s[i]);LL l = 0, r = 2e9; //最坏情况是2e9while(l < r) {LL mid = l + r >> 1;if(check(mid)) r = mid;else l = mid + 1;}cout << r;return 0;
}
（多路合并）
1262.鱼塘钓鱼
思路
枚举最后一次钓鱼的鱼塘， 传入参数（第k个鱼塘， 钓鱼时间）
代码如下
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int T, n;
int s[N], d[N], t[N], spend[N];
int get_fish(int k) { //在第k个鱼塘当前能钓鱼数量return max(0, s[k] - spend[k] * d[k]);
}
int work(int n, int T) {int res = 0;memset(spend, 0, sizeof spend);for(int i = 0; i < T; i++) { //一共枚举T次，T分钟则可选择钓T次int t = 1; //循环判断哪个鱼塘当前能钓鱼数最多for(int j = 2; j <= n; j++)if(get_fish(j) > get_fish(t))t = j;res += get_fish(t); //答案加上此时钓鱼数量spend[t]++; //当前鱼塘钓鱼时间++}return res;
}
int main () {scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d", &s[i]);for(int i = 1; i <= n; i++) scanf("%d", &d[i]); //走到第一个鱼塘不用时间for(int i = 2; i <= n; i++) cin >> t[i], t[i] += t[i - 1];cin >> T;int res = 0;// 枚举最后走到哪个鱼塘for(int i = 1; i <= n; i++) res = max(res, work(i, T - t[i])); //最后走到第i个鱼塘，钓鱼时间为T-t[i]cout << res;return 0;
}
4656.技能升级
题目：
思路分析：
代码和注释具体如下
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m;
int a[N], b[N];
bool check(int mid) {LL res = 0;for(int i = 0; i < n; i++)if(a[i] >= mid)res += (a[i] - mid) / b[i] + 1; //对于第i个技能所加的次数 ：差值 / 公差 + 1，因为差值为0时，还需要加一次if(res >= m) return true; //判断对于最后一次为mid值所对应加技能的总次数是否满足要求m次return false;
}
int main() {scanf("%d%d", &n, &m);//m 的范围太大， 故从n下手，也就是枚举加的技能点值，二分答案for(int i = 0; i < n; i++) scanf("%d%d", &a[i], &b[i]);int l = 0, r = 1e6; //左右边界（最后一次(m)加的技能点）while(l < r) {// l 和 r 的更新，***关键***//这里的话由于所加技能点是从大到小排序进行选择的，故答案必然是[mid,...]的区间（mid对应的值可能不止一个），而小于mid的不符合int mid = l + r + 1 >> 1;if(check(mid)) l = mid;else r = mid - 1;}LL res = 0, cnt = 0; //次数，答案for(int i = 0; i < n; i++) {if(a[i] > r) { // r 即为最后一次加的技能点数int s = (a[i] - r) / b[i] + 1; //第i个技能所加次数int an = a[i] - (s - 1) * b[i]; //最后一次升级的点数res += (LL)(a[i] + an) * s / 2; //等差数列公式求出所加技能点和cnt += s; //累加加技能次数}}LL ans = res - (cnt - m) * r; //最后一个数值可能加的次数不止一次，故需要特殊处理cout << ans;return 0;
}
这篇关于蓝桥杯备赛之二分专题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
