赤峰网站开发,做创意美食的视频网站有哪些,推广普通话的重要意义,设计理念题目链接https://www.acwing.com/file_system/file/content/whole/index/content/4317/ 当求左端点时#xff0c;条件是a【mid】大于等于x#xff0c;并把右端点缩小。
当求右端点时#xff0c;条件是a【mid】小于等于x#xff0c;并把左端点扩大。
1.确定一个区间…题目链接https://www.acwing.com/file_system/file/content/whole/index/content/4317/ 当求左端点时条件是a【mid】大于等于x并把右端点缩小。
当求右端点时条件是a【mid】小于等于x并把左端点扩大。
1.确定一个区间使得目标值一定在区间中
2.找一个性质满足 1性质具有二段性 2答案是二段性的分界点
3.整数二分处理红色右端点和绿色左端点 //代码1右端点
int l0,rn;
while(l r){int mid (lr1) 1;if(在红色段){l mid;}else r mid - 1;
}
//代码2左端点绿色
if是绿的说明ans在【了m】
int l0,rn;
while(lr){int mid lr 1;if(是绿的){r mid;}else l mid 1;
}例题
在这道题中因为开始已经求出左端点了所以求右端点时l可以不动只更新r为n-1 0402重写
#includealgorithm
#includeiostream
#includecstring
#includequeue
#includecmathusing namespace std;
//要求左边界右边界
int n;
int a[100010];
int q;int main()
{scanf(%d%d,n,q);for(int i0;in;i){scanf(%d,a[i]);}while(q--){int x;scanf(%d,x);int l0,rn-1;while(lr){int mid lr 1;if(a[mid] x){r mid;}else{l mid 1;}}if(a[l] x){printf(%d ,l);l 0;r n-1;while(lr){int mid lr1 1;if(a[mid] x){l mid;}else r mid - 1;}if(a[l] x){printf(%d\n,l);}}else{printf(-1 -1\n);}}return 0;
}
代码
#includealgorithm
#includeiostream
#includecstring
#includequeue
#includecmathusing namespace std;int n,k;
int a[100010];int main()
{scanf(%d%d,n,k);for(int i0;in;i){scanf(%d,a[i]);}while(k--){int q;scanf(%d,q);//找区间左端点int l0,rn-1;while(lr){int mid lr 1;if(a[mid] q)//中位数大于q说明右端点在左半段{r mid;}else l mid 1;}if(a[l] q){coutl ;//右端点l 0,r n-1;while(l r){int mid (l r 1) 1;if(a[mid] q){l mid;}else r mid - 1;}if(a[l] q){coutlendl;}}else {cout-1 -1endl;}}return 0;
}
