当前位置: 首页 > ai >正文

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[1i]当中的最小值

推导就是 P [ i ] = m i n ( P [ i − 1 ] , A [ i ] ) P[i]=min(P[i-1],A[i]) P[i]=min(P[i1],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;
}
http://www.xdnf.cn/news/7949.html

相关文章:

  • 《对话记忆的进化史:智能体大模型如何实现跨轮次的深度交互》
  • 国酒华夏实业酒水供应链:全品类覆盖打造一站式购销平台
  • 第四十三节:人脸检测与识别-人脸识别基础 (Eigenfaces, Fisherfaces, LBPH)
  • Selenium自动化测试终极指南:从原理到实战
  • 【Python生成器全解析】从基础到高阶应用实战
  • C语言—Linux环境下CMake设置库(动态/静态)
  • 借助IEDA ,Git版本管理工具快速入门
  • 多线程(七)
  • 开疆智能Profinet转RS485网关连接工业型土壤水分温度传感器 配置案例
  • 如何在 Windows 10 或 11 上安装 Adminer?
  • 非欧空间计算加速:图神经网络与微分几何计算的GPU优化(流形数据的内存布局优化策略)
  • MEMO数据DID与ZK技术:赋能RWA代币化与可信流通的新基石
  • BI 大屏是什么意思?具体应用在哪些方面?
  • 全球气体压力调节器市场深度洞察:技术演进、区域竞争与可持续发展路径(2025-2031)
  • 洛谷P1226 【模板】快速幂
  • VRRP 协议
  • SQL优化学习笔记
  • 微店平台店铺商品接口开发指南
  • 【JavaScript异步编程终极指南】从回调地狱到Async/Await的实战突围
  • 动态库和静态库
  • NHANES最新指标推荐:α-Klotho
  • BUUCTF——Web1
  • 第十节第四部分:常见API:秒杀案例、Calendar
  • 学习黑客了解5分钟了解中间人攻击(MITM)
  • 软件的技术架构、应用架构、业务架构、数据架构、部署架构
  • Nginx核心功能深度解析与实战指南
  • Java基础 集合框架 Map接口和抽象类AbstractMap
  • Java 代码生成工具:如何快速构建项目骨架?
  • Redis队列与Pub/Sub方案全解析:原理、对比与实战性能测试
  • 基于MDX的在线文档实时编译方案