蓝桥杯专项复习——二分

目录

二分查找、二分答案基础知识

二分查找模版

【模版题】数的范围

借教室

---

二分查找、二分答案基础知识

二分查找模版

【模版题】数的范围

输入样例

6 3
1 2 2 3 3 4
3
4
5

输出样例

3 4
5 5
-1 -1

思路：

对应两个模版，起始位置是对应第一个模版，即后面的都符合
终止位置对应第二个模拟，即前面的符合

#include<bits/stdc++.h>
#define int long long
using namespace std;const int N=100000+10;int a[N];signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,q;cin>>n>>q;for(int i=0;i<n;i++)cin>>a[i];while(q--){int x;cin>>x;int l=0,r=n-1;while(l<r)//查找起始位置，右边符合 {int mid=(l+r)/2;if(a[mid]>=x)r=mid;elsel=mid+1;}if(a[l]!=x)//不存在cout<<"-1 -1"<<endl;else//查找终止位置 {cout<<l<<' ';//将起始位置输出 l=0,r=n-1;while(l<r){int mid=(l+r+1)/2;if(a[mid]<=x)l=mid;elser=mid-1;}//不用再判断是否存在 //输出终止位置 cout<<l<<endl;} }return 0;} 

借教室

输入样例1

4 3
2 5 4 3
2 1 3
3 2 4
4 2 4

输出样例1

2

说明1

第一份订单满足后，这四天剩余的教室数为{0，3，2，3}
第二份订单要求第二天到第四天每天提供3个教室，而第三天剩余的教室数为 2，
因此无法满足。分配停止，通知第二个申请人修改订单。

输入样例2

4 1
2 5 4 3
2 1 3

输出样例2

0

思路：

遍历订单，再对所遍历到的订单从第一个1开始进行判断。

如果直接枚举每一个订单是O(n)，再判断又是O(n)，时间复杂度就会是O(n^2)，会超时，需要优化。

优化：

二分和差分的结合
即通过二分来搜索不符合的点，使用差分实现check函数的判断

为什么使用二分：要求找到不符合的订单是搜索，并且如果前面的订单不满足后面的订单就直接取消，具有二段性，可以使用二分法，时间复杂度变为nlogn

为什么使用差分：一段时间其实就可以看做是一段区间，对于每个教室的申请，其实就是区间修改，完全符合差分条件

 满足的条件是申请教室小于空闲教室，模版1符合
本题重点其实还是差分，二分只是优化了时间复杂的，实际的判断功能是通过差分实现。

表示是否全部分配完的方案：即特判
令r=m+1，表示有m个订单，当退出循环时l=m+1表示所有m个订单都可分配教室，就输出0；如果r=m，结束当l=m时不清楚第m个订单是否分配到

#include<iostream>
#include<bits/stdc++.h>
#define int long long using namespace std;const int N=1000000+10;
int n,m;
int a[N],b[N];
int c[N],l[N],r[N];bool check(int x)
{//对每次的订单都是从1开始到x，且内容都可以实现更新 for(int i=1;i<=n;i++)b[i]=a[i]-a[i-1];//构建a的差分数组//实现对a数组的特定范围都减去cfor(int i=1;i<=x;i++)//对第1~x个订单进行操作 {  b[l[i]]-=c[i];b[r[i]+1]+=c[i];} for(int i=1;i<=n;i++){b[i]+=b[i-1];//将差分数累加，其实是a[i] if(b[i]<0)//如果a[i]<0相当于教室数不足return true; }return false;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i]; //每天可借的订单数for(int i=1;i<=m;i++)//订单数据 ，这里先导入是为了后面使用差分对订单进行判断 cin>>c[i]>>l[i]>>r[i];//题目是要求找到不符合的订单而且订单具有二段性//最快的方法是使用二分进行查找 int l=1,r=m+1;//对订单进行遍历  while(l<r){int mid=(l+r)/2;//判断第1~第mid个订单是否符合题意//这里是将申请教室小于空闲教室作为答案//即左边为所符合的答案，使用模版1 if(check(mid)) //当教室不足时为true，r=mid即将该订单舍去，遍历前面的订单 r=mid;else //当1~mid订单符合时左范围增大，使得查询订单数向后挪 //当所有都符合时l==r==m+1 l=mid+1; } //结束条件是l==r if(l==m+1)cout<<'0'<<endl;elsecout<<r<<endl;return 0;}