行业知识
算法刷题day20：二分
目录
- 引言
- 概念
- 一、借教室
- 二、分巧克力
- 三、管道
- 四、技能升级
- 五、冶炼金属
- 六、数的范围
- 七、���佳牛围栏
引言
这几天一直在做二分的题，都是上了难度的题目，本来以为自己的二分水平已经非常熟悉了，没想到还是糊涂了一两天才重新想清楚，想明白，还是得继续不断地刷题，把这些类型的题刷明白，刷透了，就可以了，加油！
概念
一般只有这两种情况，具体模板可以参考之前的博客二分，再特殊一点的就是本篇博客的第五、六题了，但看我的解析，都是一样的步骤。
一、借教室
标签：二分
思路：这道题如果用暴力来做的话就是遍历 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 32 5 4 32 1 33 2 44 2 4输出样例：-12
示例代码：
#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≤1000001≤q≤100001≤k≤10000输入样例：6 31 2 2 3 3 4345输出样例：3 45 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
上一篇：禁止进服务器怎么解决?
下一篇：怎么自建公司服务器?
