# 二分模板
//手写
void erfen()
{
//lower_bound
while(l<r)
{
int mid=(l+r)>>1;
if(check(mid))
r=mid;
else
l=mid+1;
}
//-------------分割线---------------------
//upper_bound
while(l<=r)
{
int mid=((l+r)>>1)+1;
if(check(mid))
l=mid;
else
r=mid-1;
}
return;
}
上面是手写的 和
例题：导弹拦截
代码如下:
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=100001;
int f[N];
int f1[N];
int d[N];
int n,ans,ans1;
int main()
{
while((scanf("%d",&d[++n]))!=EOF);
n--;
int len=1,len1=1;
f[1]=f1[1]=d[1];
for(int i=2;i<=n;i++)
{
if(f[len]>=d[i])
f[++len]=d[i];
else
{
int wz=upper_bound(f+1,f+1+len,d[i],greater<int >())-f;
f[wz]=d[i];
}
if(f1[len1]<d[i])
f1[++len1]=d[i];
else
{
int wz=lower_bound(f1+1,f1+1+len1,d[i])-f1;
f1[wz]=d[i];
}
}
printf("%d\n%d\n",len,len1);
return 0;
}
二分还有另一种运用方式即二分查找
例题：奶牛晒衣服
xxxxxxxxxx struct biglong{ int d[N],fh; void print() { d[1]*=fh; for(int i=1;i<=d[0];i++) printf("%d",d[i]); printf("\n"); } bool operator < (const biglong & ot) const { if(d[0]==ot.d[0]) { for(int i=1;i<=d[0];i++) { if(d[i]==ot.d[i]) continue; return d[i]<ot.d[i]; } } return d[0]<ot.d[0]; } biglong operator + (biglong & ot) { biglong t; memset(t.d,0,sizeof(t.d)); for(int a=1,b=d[0];a<b;a++,b--) swap(d[a],d[b]); for(int a=1,b=ot.d[0];a<b;a++,b--) swap(ot.d[a],ot.d[b]); int borrow=0; t.d[0]=max(d[0],ot.d[0]); for(int i=1;i<=t.d[0];i++) { t.d[i]=borrow+d[i]+ot.d[i]; if(t.d[i]>=10) borrow=t.d[i]/10,t.d[i]%=10; else borrow=0; } if(borrow>0) t.d[0],t.d[t.d[0]]=borrow; for(int a=1,b=d[0];a<b;a,b--) swap(d[a],d[b]); for(int a=1,b=ot.d[0];a<b;a++,b--) swap(ot.d[a],ot.d[b]); for(int a=1,b=t.d[0];a<b;a++,b--) swap(t.d[a],t.d[b]); return t; } biglong operator * (biglong & ot) { biglong t; memset(t.d,0,sizeof(t.d)); for(int a=1,b=d[0];a<b;a++,b--) swap(d[a],d[b]); for(int a=1,b=ot.d[0];a<b;a++,b--) swap(ot.d[a],ot.d[b]); for(int i=1;i<=d[0];i++) { for(int j=1;j<=ot.d[0];j++) { t.d[i+j-1]+=d[i]ot.d[j]; t.d[i+j]+=t.d[i+j-1]/10; t.d[i+j-1]%=10; } } t.d[0]=d[0]+ot.d[0]; while(t.d[t.d[0]]==0) t.d[0]--; for(int a=1,b=t.d[0];a<b;a++,b--) swap(t.d[a],t.d[b]); for(int a=1,b=d[0];a<b;a++,b--) swap(d[a],d[b]); for(int a=1,b=ot.d[0];a<b;a++,b--) swap(ot.d[a],ot.d[b]); return t; }};biglong zero;biglong cut(biglong x,biglong y){ biglong t; memset(t.d,0,sizeof(t.d)); if(x<y) { biglong temp=zero; temp=x,x=y,y=temp; t.fh=-1; } else t.fh=1; for(int a=1,b=x.d[0];a<b;a++,b--) swap(x.d[a],x.d[b]); for(int a=1,b=y.d[0];a<b;a++,b--) swap(y.d[a],y.d[b]); int maxn=max(x.d[0],y.d[0]); for(int i=1;i<=maxn;i++) { if(x.d[i]<y.d[i]) { x.d[i+1]--; x.d[i]+=10; } t.d[i]=x.d[i]-y.d[i]; } while(t.d[maxn]==0) maxn--; t.d[0]=maxn; if(maxn<0) memset(t.d,0,sizeof(t.d)),t.d[0]=1; for(int a=1,b=t.d[0];a<b;a++,b--) swap(t.d[a],t.d[b]); return t;}biglong mul(biglong x,int v){ biglong ans=zero; for(int a=1,b=x.d[0];a<b;a++,b--) swap(x.d[a],x.d[b]); int borrow=0; for(int t=1;t<=x.d[0] || borrow;t++) { ans.d[t]=x.d[t]v+borrow; borrow=ans.d[t]/10; ans.d[t]%=10; ans.d[0]; } for(int a=1,b=x.d[0];a<b;a,b--) swap(x.d[a],x.d[b]); for(int a=1,b=ans.d[0];a<b;a++,b--) swap(ans.d[a],ans.d[b]); return ans;}biglong divison(biglong x,int cut){ biglong ans1=zero,ans2=zero; int borrow=0; for(int i=1;i<=x.d[0];i++) { ans1.d[i]=(borrow10+x.d[i])/cut; borrow=(borrow10+x.d[i])%cut; } int len=1; while(ans1.d[len]==0 && len<x.d[0]) len++; for(int i=1;i<=x.d[0]-len+1;i++) ans2.d[i]=ans1.d[i+len-1]; ans2.d[0]=x.d[0]-len+1; return ans2;}c++
#include <bits/stdc++.h>
using namespace std;
const int N=500001;
int n,A,B,l,r,sum;
int wet[N];
bool check(int tim)
{
int temp=tim;
for(int i=1;i<=n;i++)
{
if(tim*A>=wet[i])
continue;
else
temp-=(wet[i]-A*tim)%B==0?(wet[i]-A*tim)/B:(wet[i]-A*tim)/B+1;
}
if(temp<0)
return false;
else
return true;
}
int main()
{
scanf("%d %d %d",&n,&A,&B);
for(int i=1;i<=n;i++)
scanf("%d",&wet[i]);
l=0,r=500001;
while(l<r)
{
int mid=(l+r)/2;
if(check(mid))
r=mid;
else
l=mid+1;
}
printf("%d\n",l);
return 0;
}
