AKSZ-二分算法
2024-06-02 18:17:36
发布于:广东
第三课
1.竞赛技巧
文件提交
#include<bits/stdc++/h>
using namespace std;
int main(){
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
fclose(stdin);
fclose(stdout);
}
关闭同步流
ios::sync_with_stdio(0);
cin.tie(0)
手写读入
inline int read(){
int x=0;f=1;char ch=getchar();
while{ch<'0'||ch>'9'}{if(ch=='-')f=-1;ch=getchar();}
while{ch>='0'&&ch<='9'}{x=x*10+ch-'0';ch=getchar();}
}
随机数
using namespace std;
int main(){
mt19937 rnd(time(NULL));
int x = 1 + rnd ()%10;//生成1~10的数据
cout<<x<<endl;
return 0;
}
//在编译中加-std=c++11
考试诀窍
1.只能敲暴力
2.先敲正解,调试过样例,文件也过
3.暴力对拍
4.freeopen()p;
2.二分法
例:
第一个大于x的数
题目描述
给定一个升序序列(元素可能会重复),要在这个序列中查找第一个大于 x 的元素的下标(下标从 1 开始)。
题目保证:所有整数均在 int 的表示范围内。
提示:此为二分查找的练习题,要用二分查找完成。
输入格式
输入有 3 行。第 1 行输入 n(0<n≤100)。
第 2 行输入 n 个整数,即升序的序列。
第 3 行输入整数 x,即待查找的数。
输出格式
输出这个序列中第一个大于 x 的元素的下标(下标从 1 开始)。
样例组输入#1
7
3 8 8 8 8 15 23
8
样例组输出#1
6
样例组输入#2
7
3 8 8 8 8 15 23
16
样例组输出#2
7
代码如下:
#include<bits/stdc++.h>
using namespace std;
int n;
int a[105];
int x;
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
cin>>x;
int l=1,r=n;//二分的上下边界
//在[l,r]闭区间内//开区间内[l,r]不包括最后一个结点
int ans=-1;
while(l<=r){
int mid=(l+r)>>1;
if(a[mid]<=x){
ans=mid;
l=mid+1;
}else{
r=mid-1;
}
}
cout<<ans+1;//ans是最后一个小于等于x的数,因此ans还要加上1
return 0;
}
lower_bound()与upper_bound
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[]={1,2,3,4,5,6,7,8};
int b=4;
int n=8;
int id=lower_bound(a,a+8,b)-a;
cout<<id;
return 0;
}
//适用于升序数组 lower_bound()
//lower_bound(数组开头下标,数组结尾下标+1,待查元素)-数组第0个下标开头
//返回值是第一个大于等于待查元素的下标
//适用于升序数组 upper_bound()
//upper_bound(数组开头下标,数组结尾下标+1,待查元素)-数组第0个下标开头
//返回值是第一个大于待查元素的下标
如果找不到符合的数,便会输出a数组结尾下标+1
小数二分
例:
平方根
题目描述
小码君最近在研究二分查找算法,发现一个非负整数 n 的算术平方根,也可以通过二分查找来计算。请你使用二分查找完成此任务吧。
输入格式
输入一个非负整数 n 。
输出格式
输出 n 的实数平方根,若存在,输出非负平方根,并保留 5 位小数即可,若不存在,输出 -1。
样例组输入#1
4
样例组输出#1
2.00000
样例组输入#2
2
样例组输出#2
1.41421
代码如下
#include<bits/stdc++.h>
using namespace std;
int n;
int a[105];
int x;
int main(){
cin>>n;
if(n<0)cout<<-1;
double l=0.0,r=n;
double ans=-1;
double eps=1e-6;//精度控制
while(abs(r-l)>=eps){
double mid=(l+r)/2.0;
if(mid*mid<=n){
ans=mid;
l=mid;
}else{
r=mid;
}
}
if(n==0)cout<<0;
if(n>0)printf("%.5f",ans);
return 0;
}
反码
正数:不变
复数:除符号位外每一位取反
补码
这里空空如也
有帮助,赞一个