算法刷题day20：二分
目录
- 引言
- 概念
- 一、借教室
- 二、分巧克力
- 三、管道
- 四、技能升级
- 五、冶炼金属
- 六、数的范围
- 七、最佳牛围栏
- 八、套餐设计
- 九、牛的学术圈I
- 十、我在哪？
引言
这几天一直在做二分的题，都是上了难度的题目，本来以为自己的二分水平已经非常熟悉了，没想到还是糊涂了一两天才重新想清楚，想明白，还是得继续不断地刷题，把这些类型的题刷明白，刷透了，就可以了，加油！
（图片来源网络，侵删）概念
一般只有这两种情况，具体模板可以参考之前的博客二分，再特殊一点的就是本篇博客的第五、六题了，但看我的解析，都是一样的步骤。
一、借教室
标签：二分
思路：这道题如果用暴力来做的话就是遍历 m m m 个订单，每个订单然后去判断是否正确，去判断没天中的订单是否满足要求，就这样也是 1 0 12 10^{12} 1012 明显超时了。可以用二分来做，因为这个订单是具有单调性的，假设第 k k k 个订单是第一个不满足要求的，那么之后的订单也是不满足要求的，判断依据就是定义一个天数数组 b [ i ] b[i] b[i] ，每天的订单数是不能超过 w [ i ] w[i] w[i] 的，所以可以用二分检查条件从而判断出第一个不满足的，然后再 s j ∼ t j s_j\sim t_j sj∼tj天要用 d j d_j dj个教室可以用差分来做，这样就可以了。
这相当于一个模型：有多个订单，每天进行多个操作，问订单会不会满足条件.
题目描述：
（图片来源网络，侵删）在大学期间，经常需要租借教室。 大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。 教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。 面对海量租借教室的信息，我们自然希望编程解决这个问题。 我们需要处理接下来 n 天的借教室信息，其中第 i 天学校有 ri 个教室可供租借。 共有 m 份订单，每份订单用三个正整数描述，分别为 dj,sj,tj，表示某租借者需要从第 sj 天到第 tj 天租借教室（包括第 sj 天和 第 tj 天），每天需要租借 dj 个教室。 我们假定，租借者对教室的大小、地点没有要求。 即对于每份订单，我们只需要每天提供 dj 个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。 借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。 如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。 这里的无法满足指从第 sj 天到第 tj 天中有至少一天剩余的教室数量不足 dj 个。 现在我们需要知道，是否会有订单无法完全满足。 如果有，需要通知哪一个申请人修改订单。 输入格式 第一行包含两个正整数 n,m，表示天数和订单的数量。 第二行包含 n 个正整数，其中第 i 个数为 ri，表示第 i 天可用于租借的教室数量。 接下来有 m 行，每行包含三个正整数 dj,sj,tj，表示租借的数量，租借开始、结束分别在第几天。 每行相邻的两个数之间均用一个空格隔开。 天数与订单均用从 1 开始的整数编号。 输出格式 如果所有订单均可满足，则输出只有一行，包含一个整数 0。 否则（订单无法完全满足）输出两行，第一行输出一个负整数 −1，第二行输出需要修改订单的申请人编号。 数据范围 1≤n,m≤106,0≤ri,dj≤109,1≤sj≤tj≤n 输入样例： 4 3 2 5 4 3 2 1 3 3 2 4 4 2 4 输出样例： -1 2
示例代码：
#include using namespace std; typedef long long LL; const int N = 1e6+10; int n, m; int w[N]; int d[N], s[N], t[N]; LL b[N]; bool check(int mid) { memset(b, 0, sizeof b); for(int i = 1; i b[s[i]] += d[i]; b[t[i]+1] -= d[i]; } for(int i = 1; i b[i] += b[i-1]; if(b[i] w[i]) return true; } return false; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin > n >> m; for(int i = 1; i > w[i]; for(int i = 1; i > d[i] >> s[i] >> t[i]; int l = 1, r = m; while(l > 1; if(check(mid)) r = mid; else l = mid + 1; } if(check(r)) { cout cout LL s = 0; for(int i = 1; i s += ((LL)h[i] / mid) * (w[i] / mid); if(s = k) return true; } return false; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin n k; for(int i = 1; i > w[i]; int l = 1, r = 1e5; while(l > 1; if(check(mid)) l = mid; else r = mid - 1; } cout int cnt = 0; for(int i = 1; i if(mid = S[i]) { int t = mid - S[i]; int l = max(1, L[i] - t), r = min((LL)len, (LL)L[i] + t); segs[cnt++] = {l,r}; } } sort(segs, segs+cnt); int l = -2e9, r = -2e9; for(int i = 0; i > len; for(int i = 1; i > L[i] >> S[i]; int l = 0, r = 2e9; // 等到1e9开阀门，再经过1e9从左边流到右边 while(l > 1; if(check(mid)) r = mid; else l = mid + 1; } cout ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin n >> m; for(int i = 1; i cin > a[i] >> b[i]; heap.push({a[i], b[i]}); } LL res = 0; while(m-- && heap.size()) { auto t = heap.top(); heap.pop(); res += t.x; if(t.x - t.y t.x-t.y, t.y}); } cout LL s = 0; for(int i = 1; i if(a[i] = mid) { s += (a[i] - mid) / b[i] + 1; if(s = m) return true; } } return false; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin n >> m; for(int i = 1; i > a[i] >> b[i]; int l = 0, r = 1e6; // l可能取0，即全部包含进去 while(l > 1; if(check(mid)) l = mid; else r = mid - 1; } LL res = 0, cnt = 0; for(int i = 1; i if(a[i] = r) { int c = (a[i] - r) / b[i] + 1; int end = a[i] - (c - 1) * b[i]; cnt += c; res += (LL)(a[i] + end) * c / 2; } } cout for(int i = 1; i // 说明在左半边 if(a[i] / mid b[i]) return false; // 最小值，满足条件的是右半边，mid越大值越小，所以当大于b[i]时就不满足条件了 } return true; } bool check2(int mid) { for(int i = 1; i if(a[i] / mid > b[i]; int r1, r2; int l = 1, r = 1e9; // 因为a[i], b[i]的值可能为1e9,1 while(l > 1; // 这里的check判断的为是否在右半边 if(check1(mid)) r = mid; // 找最小值，发现右边是条件一样的，所以 r = mid else l = mid + 1; } r1 = r; l = 1, r = 1e9; while(l > 1; if(check2(mid)) l = mid; // 找最大值，发现左边和自己的条件是一样的，所以l = mid else r = mid - 1; } r2 = r; cout 1 int mid=l+r>>1那，要改成 i n t m i d = l + r + 1 > > 1 int\ mid = l + r + 1 >> 1 int mid=l+r+1>>1，否则会有边界问题。然后说一下最大值，再梳理一遍，其最大值，满足相同条件的在左部分，虽然只有一部分但只要这么想就是对的， c h e c k check check 为 a [ m i d ] ≤ x a[mid] \leq x a[mid]≤x ，因为在满足条件的在左边所以 l = m i d l = mid l=mid ，然后就是 r = m i d − 1 r = mid - 1 r=mid−1 ，再在二分 m i d mid mid 那加一。
题目描述：
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。 对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。 如果数组中不存在该元素，则返回 -1 -1。 输入格式 第一行包含整数 n 和 q，表示数组长度和询问个数。 第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。 接下来 q 行，每行包含一个整数 k，表示一个询问元素。 输出格式 共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。 如果数组中不存在该元素，则返回 -1 -1。 数据范围 1≤n≤100000 1≤q≤10000 1≤k≤10000 输入样例： 6 3 1 2 2 3 3 4 3 4 5 输出样例： 3 4 5 5 -1 -1
示例代码：
#include using namespace std; typedef long long LL; const int N = 1e5+10; int n, q; int a[N]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q; for(int i = 0; i > a[i]; while(q--) { int x; cin >> x; int r1 = -1, r2 = -1; int l = 0, r = n - 1; // 注意看好起始位置从几开始的 while(l > 1; if(a[mid] >= x) r = mid; // 先看点，然后看相同条件的区间在哪来判断check，然后区间在右就是r = mid else l = mid + 1; // 在左就是l = mid，其余的else和+1跟着变就行 } if(a[r] == x) r1 = r; l = 0, r = n - 1; while(l > 1; if(a[mid] cin n f; for(int i = 1; i cin a[i]; s[i] = s[i-1] + a[i]; } int res = -2e9; for(int i = 1; n - i + 1 >= f; ++i) { for(int j = i + f - 1; j res = max((double)res, (double)(s[j] - s[i-1]) / (j - i + 1) * 1000); } } cout for(int i = 1; i minv = min(minv, sum[i]); if(sum[j] = minv) return true; } return false; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin n m; for(int i = 1; i > cow[i]; double l = 0, r = 2000; while(r - l > 1e-5) { double mid = (l + r) / 2; if(check(mid)) l = mid; else r = mid; } cout int res = 0; for(int i = 0; i n >> m; for(int i = 0; i > t; w[t]++; } int l = 0, r = 100; while(l > 1; if(check(mid)) l = mid; else r = mid - 1; } cout int res = 0, t = 0; for(int i = 0; i > n >> m; for(int i = 0; i > a[i]; int l = 0, r = 1e5; while(l > 1; if(check(mid)) l = mid; else r = mid - 1; } cout unordered_map string t2 = str.substr(i, mid); if(mmap.count(t2)) return false; mmap[t2]++; } return true; } int main() { cin n >> str; int l = 1, r = n; while(l > 1; if(check(mid)) r = mid; else l = mid + 1; } cout
还没有评论，来说两句吧...