二分
两个常见的二分做法:直接二分答案、排序+二分
直接二分答案
题1 730. 机器人跳跃问题
#include<iostream>
using namespace std;
const int N=100010;
int n;
int h[N];
bool check(int t)
{
for(int i=0;i<n;++i)
{
t+=t-h[i];
if(t<0) return false;
if(t>N) return true;
}
return true;
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;++i) scanf("%d",&h[i]);
int l=-1,r=N;
while(r-l>1)
{
int mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid;
}
printf("%d",r);
return 0;
}
题2 1227. 分巧克力
#include<iostream>
using namespace std;
const int N=100010;
int n,k;
int h[N],w[N];
bool check(int mid)
{
int res=0;
for(int i=0;i<n;++i)
res+=(h[i]/mid)*(w[i]/mid);
return res>=k;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;++i)
scanf("%d%d",&h[i],&w[i]);
int l=0,r=N;
while(r-l>1)
{
int mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
printf("%d",l);
return 0;
}
排序+二分
题1 1221. 四平方和
#include<iostream>
#include<algorithm>
using namespace std;
const int N=5000010;
int n,m;
struct Node{
int s,c,d;
bool operator<(const Node& t){
if(s!=t.s) return s<t.s;
if(c!=t.c) return c<t.c;
return d<t.d;
}
}q[N];
int main()
{
scanf("%d",&n);
for(int c=0;c*c<=n;++c)
for(int d=c;c*c+d*d<=n;++d)
q[m++]={c*c+d*d,c,d};
sort(q,q+m);
for(int a=0;a*a<=n;++a)
for(int b=a;a*a+b*b<=n;++b)
{
int t=n-a*a-b*b,l=-1,r=m;
while(r-l>1)
{
int mid=(l+r)/2;
if(q[mid].s<t) l=mid;
else r=mid;
}
if(q[r].s==t)
{
printf("%d %d %d %d",a,b,q[r].c,q[r].d);
return 0;
}
}
return 0;
}
题2 1236. 递增三元组
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=100010;
int n;
int A[N],B[N],C[N];
int main()
{
scanf("%d",&n);
for(int i=0;i<n;++i) scanf("%d",A+i);
for(int i=0;i<n;++i) scanf("%d",B+i);
for(int i=0;i<n;++i) scanf("%d",C+i);
sort(A,A+n),sort(C,C+n);
LL res=0;
for(int i=0;i<n;++i)
{
int x1=lower_bound(A,A+n,B[i])-A-1;
int x2=upper_bound(C,C+n,B[i])-C;
res+=(LL)(x1+1)*(n-x2);
}
printf("%lld",res);
return 0;
}
前缀和
使用场景:预处理后O(1)求连续子块和
题1 1230. K倍区间
#include<iostream>
using namespace std;
typedef long long LL;
const int N=100010;
int n,k;
LL s[N],cnt[N];
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)
scanf("%lld",&s[i]),s[i]+=s[i-1];
LL res=0;
cnt[0]=1;
for(int i=1;i<=n;++i)
res+=cnt[s[i]%k]++;
printf("%lld",res);
return 0;
}
题2 99. 激光炸弹
#include<iostream>
using namespace std;
const int N=5010;
int s[N][N];
int cnt,r;
int main()
{
scanf("%d%d",&cnt,&r);
r=min(r,5001);
int n=r,m=r;
while(cnt--)
{
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
n=max(n,x+1),m=max(m,y+1);
s[x+1][y+1]+=w;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
int res=0;
for(int i=r;i<=n;++i)
for(int j=r;j<=m;++j)
res=max(res,s[i][j]-s[i-r][j]-s[i][j-r]+s[i-r][j-r]);
printf("%d",res);
return 0;
}