蓝桥杯练习题——二分

1.借教室

思路

1.随着订单的增加，每天可用的教室越来越少，二分查找最后一个教室没有出现负数的订单编号
2.每个订单的操作是 [s, t] 全部减去 d

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e6 + 10;
int d[N], s[N], t[N], a[N];
long long b[N]; 
int n, m;int check(int mid){memset(b, 0, sizeof(b));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] > a[i]) return 0;}return 1;
}int main(){scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);for(int i = 1; i <= m; i++) scanf("%d%d%d", &d[i], &s[i], &t[i]);int l = 0, r = m + 1;while(l + 1 < r){int mid = (l + r) / 2;if(check(mid)) l = mid;else r = mid;}// 此时 r 为第一个不满足的编号if(r == m + 1) printf("0");else printf("-1\n%d", r);return 0;
}

2.分巧克力

思路

二分巧克力边长，注意长和宽都要除以 mid，防止出现 1 * 100 除以 2 * 2的情况

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int h[N], w[N];
int n, k;int check(int mid){int sum = 0;for(int i = 1; i <= n; i++){// 注意：比如 1 * 100，mid 为 2，不可分sum += (h[i] / mid) * (w[i] / mid);}if(sum >= k) return 1;else return 0;
}int main(){scanf("%d%d", &n, &k);for(int i = 1; i <= n; i++) scanf("%d%d", &h[i], &w[i]);int l = 0, r = 1e5 + 1;while(l + 1 < r){int mid = (l + r) / 2;if(check(mid)) l = mid;else r = mid;}printf("%d", l);return 0;
}

3.管道

思路

1.二分最早打开的时间
2.合并已经打开的区间

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
pair<int, int> q[N]; // 存储左右端点
int L[N], S[N];
int n, len;int check(int mid){int cnt = 0;for(int i = 0; i < n; i++){if(mid >= S[i]){// 延伸出去的距离int t = mid - S[i];int l = max(1, L[i] - t), r = min(1ll * len, 1ll * L[i] + t);q[cnt++] = make_pair(l, r);}}//区间合并sort(q, q + cnt);int st = -1, ed = -1;for(int i = 0; i < cnt; i++){if(ed + 1 >= q[i].first) 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 = 0; i < n; i++) scanf("%d%d", &L[i], &S[i]);int l = 0, r = 2e9 + 1;while(l + 1 < r){int mid = (1ll * l + r) / 2;if(check(mid)) r = mid;else l = mid;}printf("%d", r);return 0;
}

4.技能升级

思路

1.多路归并，把所有等差数列放在一个数组，从大到小排序，选前 m 个数
2.大于等于 x 的个数一定大于等于 m 个，二分 x，x 为从大到小排名为 m 的数
3.每个数列大于等于 x 的个数为 (a - x) / b + 1
4.每个数列大于等于 x 的总和为 (首项 + 末项) * 项数 / 2

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int n, m;// 判断大于等于 mid 的个数，是否大于等于 m
int check(int mid){long long cnt = 0;for(int i = 0; i < n; i++){if(a[i] >= mid) cnt += (a[i] - mid) / b[i] + 1;}return cnt >= m;
}int main(){scanf("%d%d", &n, &m);for(int i = 0; i < n; i++) scanf("%d%d", &a[i], &b[i]);int l = 0, r = 1e6 + 1;while(l + 1 < r){int mid = (l + r) / 2;if(check(mid)) l = mid;else r = mid;}long long sum = 0, cnt = 0;for(int i = 0; i < n; i++){if(a[i] >= l){// 计算项数int c = (a[i] - r) / b[i] + 1;// 计算末项int ed = a[i] - b[i] * (c - 1);// 等差数列求和sum += 1ll * (a[i] + ed) * c / 2;     // 计算有多少项，可能有多余cnt += c;}}// 减去多余的项printf("%lld", sum - (cnt - m) * l);return 0;
}

5.冶炼金属

思路

方法1：二分左右边界
方法2：推导公式，a / x >= b，a / x < (b + 1);

// 方法1
#include<iostream>
using namespace std;
const int N = 1e4 + 10;
int a[N], b[N];
int n;// 找到最大值
int check1(int mid){for(int i = 0; i < n; i++){if(a[i] / mid < b[i]) return 0;}return 1;
}// 找到最小值
int check2(int mid){for(int i = 0; i < n; i++){if(a[i] / mid > b[i]) return 0;}return 1;
}int main(){scanf("%d", &n);for(int i = 0; i < n; i++) scanf("%d%d", &a[i], &b[i]);int l = 0, r = 1e9 + 1;while(l + 1 < r){int mid = (l + r) / 2;if(check1(mid)) l = mid;else r = mid;}int res1 = l;l = 0, r = 1e9 + 1;while(l + 1 < r){int mid = (l + r) / 2;if(check2(mid)) r = mid;else l = mid;}int res2 = r;printf("%d %d", res2, res1);return 0;
}// 方法2
#include<iostream>
using namespace std;
const int N = 1e4 + 10;
int a, b;
int n;int main(){scanf("%d", &n);int res1 = 1, res2 = 1e9;for(int i = 0; i < n; i++){scanf("%d%d", &a, &b);res1 = max(res1, a / (b + 1) + 1);res2 = min(res2, a / b);}printf("%d %d", res1, res2);return 0;
}

6.数的范围

思路

二分左右边界

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n, q;// 找最小值
int check1(int mid, int k){return a[mid] < k;
}// 找最大值
int check2(int mid, int k){return a[mid] <= k;
}int main(){scanf("%d%d", &n, &q);for(int i = 0; i < n; i++) scanf("%d", &a[i]);int k;while(q--){scanf("%d", &k);int l = -1, r = n;while(l + 1 < r){int mid = (l + r) / 2;if(check1(mid, k)) l = mid;else r = mid;}int res1 = r;l = 0, r = n;while(l + 1 < r){int mid = (l + r) / 2;if(check2(mid, k)) l = mid;else r = mid;}int res2 = l;if(a[res1] == k && a[res2] == k) printf("%d %d\n", res1, res2);else printf("-1 -1\n");}return 0;
}

7.最佳牛围栏

思路

1.二分平均值，每个数先减去平均值，转化成是否存在长度大于等于 f 的非零子段和
2.舍去很小的前缀和，保留大的前缀和

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
double a[N], s[N];
int n, f;int check(double mid){double res = 1e9, ans = -1e9;for(int i = f; i <= n; i++){// 可以舍去的前缀和res = min(res, s[i - f]);// 保留的前缀和ans = max(ans, s[i] - res);}return ans >= 0;
}int main(){scanf("%d%d", &n, &f);for(int i = 1; i <= n; i++){scanf("%lf", &a[i]);}double l = 0, r = 2001;while(l + 1e-5 < r){double mid = (l + r) / 2;for(int i = 1; i <= n; i++){s[i] = s[i - 1] + a[i] - mid;}if(check(mid)) l = mid;else r = mid;}// l + 1e-5 = rint ans = r * 1000;printf("%d", ans);return 0;
}