二分查找法

 P2249 【深基13.例1】查找

答案

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1000010;//10e+10int read(){//快读int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f;
}
int a[MAXN];int main(){int n=read(),m=read();for(int i=1;i<=n;i++)a[i]=read();while(m--){int x=read();int ans=lower_bound(a+1,a+n+1,x)-a;//别忘了-aif(x!=a[ans])printf("-1 ");//注意空格else printf("%d ",ans);//注意空格}return 0;}

P1102 A-B 数对

解答

#include <bits/stdc++.h>
using namespace std;long a[200001];
long N,C,ans;
int main(){cin>>N>>C;for(int i=1;i<=N;i++){cin>>a[i];}sort(a+1,a+N+1);for(int i=1;i<=N;i++){ans+=((upper_bound(a+1,a+N+1,a[i]+C)-a)-(lower_bound(a+1,a+N+1,a[i]+C)-a));}cout<<ans;return 0;
}

P1873 [COCI 2011/2012 #5] EKO / 砍树

题解1：二分查找法

#include<bits/stdc++.h>
using namespace std;
const long long N=10000010;
long long n,m,a[N],tmp,l,r,ans;
bool check(long long x){for(long long i=1;i<=n;i++)if(x<a[i])tmp+=a[i]-x;return m<=tmp;//骚写法，如果满足条件则返回1 
}
int main(){cin>>n>>m;for(long long i=1;i<=n;i++)cin>>a[i],r=r>a[i]?r:a[i];while(l<=r){long long mid=(l+r)>>1;tmp=0;if(check(mid))l=(ans=mid)+1;//在右区间查找，同时更新答案 else r=mid-1;//在左区间查找 }cout<<ans;return 0;
}

P1024 [NOIP2001 提高组] 一元三次方程求解

题解

#include <bits/stdc++.h>
using namespace std;double a,b,c,d;
double fc(double x)
{return a*x*x*x+b*x*x+c*x+d;
}
int main()
{double l,r,m,x1,x2;int s=0,i;scanf("%lf%lf%lf%lf",&a,&b,&c,&d);  //输入for (i=-100;i<100;i++){l=i; r=i+1;x1=fc(l); x2=fc(r);if(!x1) {printf("%.2lf ",l); s++;}      //判断左端点，是零点直接输出。//不能判断右端点，会重复。if(x1*x2<0)                             //区间内有根。{while(r-l>=0.001)                     //二分控制精度。{m=(l+r)/2;  //middleif(fc(m)*fc(r)<=0) l=m; else r=m;   //计算中点处函数值缩小区间。}printf("%.2lf ",r);  //输出右端点。s++;}if (s==3) break;             //找到三个就退出大概会省一点时间}return 0;
}