YCKC【二分查找专题】题解
数的范围题解点击跳转题目链接:数的范围
比较经典的二分查找例题,不做过多赘述。注意看二分的对象以及最终想求什么:想求尽可能大 ,那么就是最大值类型的二分;想求尽可能小,就是最小值类型的二分。注意二分的写法。不过本题要注意的是最终分出来的答案到底行不行,所以还要再检查判断一次
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6+10;
int a[N];
int main(){int n,m;cin >>n >> m;for(int i = 1; i <= n; i++) cin >> a[i];for(int i = 1; i <= m; i++){int x;cin >> x;int l = 1,r = n;while(l < r){int mid = (l + r) / 2;if(a[mid] >= x) r = mid;else l = mid + 1;}int l1 = 1,r1 = n;while(l1 < r1){int mid = (l1 + r1 + 1) / 2;if(a[mid] > x) r1 = mid - 1;else l1 = mid;}if(a[l] != x){cout << -1 << " " << -1 << endl;}else cout << l - 1 << " " << l1 - 1 << endl;}/*int l = 1, r = n;while(l < r){//最大值类型二分模板int mid = (l + r + 1) / 2;if(a[mid] > x) r = mid - 1;else l = mid; }while(l < r){//最小值类型模板int mid = (l + r) / 2;if(a[mid] >= x) r = mid;else l = mid + 1;}*/return 0;
}
查找第一次出现的位置题解点击跳转题目链接
与上一题类似,模仿写就行了
#include<bits/stdc++.h>
using namespace std;
int A[1000010];
int main() {int n, m;cin >> n >> m;int x;int l = 1;int r = n;for (int i = 1; i <= n; i++) {cin >> A[i];}for (int i = 1; i <= m; i++) {cin >> x;while (l < r) {int mid = (l + r) / 2;if (x <= A[mid]) {r = mid;} else {l = mid + 1;}}if (x == A[r]) {cout << r;} else {cout << -1;}cout << ' ';l = 1;r = n;}return 0;
}
烦恼的高考志愿点击跳转题目
因为本题估分可能超过录取线,也可能低于录取线,总之差的绝对值就是不满意度,为了计算某个估分的不满意度,实际上我们需要两个分数,
存在录取分数[i]小于等于估分且估分小于录取分数[i+1],毕竟要计算估分少了或大了两种情况的不满意度,取最小值。
我们对录取分数线排序一下,为了更好地明确范围,我们把原本录取分数数组两端新增两个值,一个极小值-1e9,一个极大值1e9,然后二分查找录取分数里面小于等于当前估分且最接近当前估分的录取分数的位置。查找到以后计算答案即可。注意本题答案最终超过int范围
#include<bits/stdc++.h>
using namespace std;
int G[100005];//估分
int F[100005]; //录取分
int main(){int n,m;scanf("%d%d",&m,&n);for(int i=1;i<=m;i++){scanf("%d",&F[i]);}sort(F+1,F+1+m);F[m+1]=1e9;F[0]=-1e9;long long int sum=0;for(int i=1;i<=n;i++){scanf("%d",&G[i]);int L=0,R=m+1;//二分左边录取分最接近估分的位置//那么估分一定在F[L]~F[L+1]里面求得最小不满意 while(L<R){int mid=(L+R+1)/2;if(F[mid]<G[i]){L=mid;}else{R=mid-1;}}sum=sum+min(abs(G[i]-F[L]),abs(F[L+1]-G[i]));}printf("%lld",sum);return 0;
}
星际蛋糕点击跳转题解
本题呢,先按题目说的把偶数都拆了吧,其实很好写,直接写个while循环就能搞定。假如是一开始 i i i位置的数是 A [ i ] A[i] A[i] 那么直接对 A [ i ] A[i] A[i]操作就好了, A [ i ] A[i] A[i]表示从左到右的第 i i i段位置最终的数字。既然涉及到一段一段数字的拆分,很显然我们能计算出某段数字的起点以及终点,这个怎么计算呢?其实就是从左到右的一个过程,每次拆完数字以后,计算出这一段数字有多少个,我们当前的总长度+1就是本段数字的起点位置,当前总长度+当前段的长度就是本段数字的终点,因为前面也有很多段数字。
计算 s u m [ i ] sum[i] sum[i]表示前 i i i段数字的终点位置,最终我们对于每个查询的 X j Xj Xj直接二分找到严格小于 X j Xj Xj且最大的位置 L L L,那么第 X j Xj Xj位置的数一定处于第 L + 1 L+1 L+1段里面
#include<bits/stdc++.h>
using namespace std;
long long int pos[200005];
long long int sum[200005];
long long int w;
int A[200005];
bool check(int x){return sum[x]<w;
}
int main(){int n,q;scanf("%d",&n);int len=0;for(int i=1;i<=n;i++){int x;scanf("%d",&A[i]);int cnt=1;while(A[i]%2==0){A[i]=A[i]/2;cnt=cnt*2;}pos[i]=len+1;//第i种数的起点len=len+cnt;//终点 sum[i]=sum[i-1]+cnt;//sum[i]表示前i种数结束的位置 }scanf("%d",&q);while(q--){scanf("%lld",&w);int L=0,R=n; while(L<R){int mid=(L+R+1)/2;if(check(mid)){L=mid;}else{R=mid-1;}}//二分找到严格小于w的位置,那么w必定处于L+1的位置里面 printf("%d\n",A[L+1]);}return 0;
}
Skibidus and Fanum Tax (hard version)点击跳转题目
这个题的区别就是 M M M取值范围是 2 e 5 2e5 2e5
意思就是说 A [ i ] A[i] A[i]的选择可以是任选一个 B [ j ] B[j] B[j]来做减法。
给你两个数组A B
A的长度N
B的长度M=2e5 课堂笔记推导 自己仔细看看 这个题要用到二分 对于每个A数组的元素A[i] 我们至多可以操作一次
从B当中选一个数,然后把A[i]变为B[j]-A[i] 先给B数组排序 A1 B[1]-A[1] 选择最小的 对于后面A[2~N] 它可以选择 A[i] B[?]>=x 你要找 B数组里面,满足这个式子最小的位置 B[1..mid....N] 二分 一分为二 B[mid]>=x 只需要logM次 就可以找到合适的B
#include<bits/stdc++.h>
using namespace std;
int A[200010],B[200010];
int main(){int t;cin>>t;while(t--){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>A[i];}for(int i=1;i<=m;i++){cin>>B[i];}sort(B+1,B+1+m);bool ok=true;A[1]=min(B[1]-A[1],A[1]);for(int i=2;i<=n;i++){int l=1,r=m;while(l<r){// 二分 int mid=(l+r)/2;if(B[mid]>=A[i-1]+A[i]){r=mid;}else l=mid+1;}if(B[r]>=A[i-1]+A[i]){ // 再次检验二分出来的答案行不行 if(A[i]>=A[i-1]){ //如果行的话,还要检查 直接保留原本的A【i】行不行 A[i]=min(A[i],B[r]-A[i]);}else{ //如果只有用操作才能行的话 那么A[i]是不是必须要变 A[i]=B[r]-A[i];}}else{//如果用操作 找不到答案 if(A[i]>=A[i-1]){ //判断不变 能不能行 continue; }ok=false;break;}}if(ok)cout<<"YES";else cout<<"NO";cout<<endl;}return 0;
}
吃寿司点击跳转题目链接
题目要读懂,意思就是 N N N个人 排成一排,等待吃寿司,每个人有个数值 A [ i ] A[i] A[i] ,接下来依次流水线过来的 M M M个寿司,寿司有个值 B [ i ] B[i] B[i] ,如果寿司 B B B的值 > = >= >= 人的 A A A值 那么这个人就是要吃寿司的。题目问,请我们确定每个寿司被谁吃掉,或者不被吃。
我们可以记录一个数据, p [ i ] p[i] p[i]表示前 i i i个人当中,最小的A值
那么对于每个寿司来说,我们看这个图
很明显,当从左往右的人越多时,前缀当中的最小A值曲线就会降低。
而我们每个寿司需要满足,它的B值>= 某个人的A值 才能被吃掉
根据这个曲线,我们很明显要找到第一个能吃这个寿司的人,也就是第一个 A值 小于等于B值的人的位置。
所以我们可以先统计 P [ i ] P[i] P[i] 记录一个前缀最小值数组, P [ i ] 表示 A [ 1 到 i ] 当中的最小值 P[i]表示A[1到i]当中的最小值 P[i]表示A[1到i]当中的最小值
推导就是 P [ i ] = m i n ( P [ i − 1 ] , A [ i ] ) P[i]=min(P[i-1],A[i]) P[i]=min(P[i−1],A[i])
然后枚举每个寿司,去 P P P数组当中二分查找即可,查找第一个<= 这个寿司的位置
找不到就是-1
#include<bits/stdc++.h>
using namespace std;
#define N 200005
int n,m,a[N],b[N],p[N];
int main(){cin>>n>>m;p[0]=1e9;for(int i=1;i<=n;i++){cin>>a[i];p[i]=min(p[i-1],a[i]);}for(int i=1;i<=m;i++)cin>>b[i];for(int i=1;i<=m;i++){//寻找第一个小于等于a[i]的b[j] int l=1,r=n;while(l<r){int mid=(l+r)/2;if(p[mid]<=b[i]){r=mid;}else l=mid+1;}if(p[r]<=b[i])cout<<r<<endl;else cout<<-1<<endl;}return 0;
} //60 60 60 45 45 45 37 37 37 22//39
运动汽车点击跳转题目链接
明白人一眼就能看出,Q次查询,每次问走了 D [ i ] D[i] D[i]要多少时间,其实就是二分,因为 D [ i ] D[i] D[i]可以处于某两个标记点中间,而每个标记点都有自己的到达时间。我们直接二分看看这个 D [ i ] D[i] D[i]在哪,用匀速运动算出那一小段时间,再加上前面的即可。问题就在于每段区间的匀速速度,这个东西你要仔细看看数据,就会发现可能达到很大很大的程度,而double无法承载这种精度,而且题目也说了向下取整
我们分析每次查询的答案无外乎是某一个标记点的时间+匀速运动一小段的时间
匀速运动的时间=一小段路程/(区间距离 除以 区间时间) 我们把除法转换一下,把分母的除法乘上去,变成 一小段路程*区间时间 除以 区间距离 这个公式就是我们的匀速运动的时间,不整除也没事,反正不整除的部分也不考虑,因为答案向下取整,所以本题算时间得这样子算,注意long long
#include<bits/stdc++.h>
using namespace std;
struct pe{long long int pos;long long int time;double v;
}A[100005];
int d;
bool check(int x,int y){if(A[x].pos>y)return true;else return false;
}
int Q[100005];
int main(){int t;scanf("%d",&t);A[0].pos=0;A[0].time=0;while(t--){int n,k,q;scanf("%d%d%d",&n,&k,&q);for(int i=1;i<=k;i++){scanf("%d",&A[i].pos);}for(int i=1;i<=k;i++){scanf("%d",&A[i].time);//A[i].v=(A[i].pos-A[i-1].pos)*1.0/(A[i].time-A[i-1].time);//之前我也是没注意到精度}A[k+1].pos=n+1;for(int i=1;i<=q;i++){scanf("%d",&Q[i]);}for(int i=1;i<=q;i++){int L=1,R=k+1;while(L<R){int mid=(L+R)/2;if(check(mid,Q[i])){R=mid; }else{L=mid+1;}} printf("%lld ",A[R-1].time+ (long long int)((Q[i]-A[R-1].pos)*(A[R].time-A[R-1].time)/(A[R].pos-A[R-1].pos)));}printf("\n");}return 0;
}