二分的两种情况附代码:
二分查找条件:单调,二段性
例题1:P1873 [COCI 2011/2012 #5] EKO / 砍树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
上代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int a[N],b[N];
int n;
long long m;
bool check(int h)
{
long long sum=0;
for(int i=1;i<=n;i++)
{
sum+=max(0,a[i]-h);
}
if(sum<m)
return false;
return true;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
int l=0,r=400000;
while(l<r)
{
int mid=(l+r+1)/2;
if(check(mid))
l=mid;
else
r=mid-1;
}
cout<<l;
return 0;
}
例题2:503. 借教室 - AcWing题库
上代码
#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
long long r[N],d[N],s[N],t[N],b[N];
long long n,m;
bool check(int mid)
{
for(long long i=1;i<=n;i++)
b[i]=r[i]-r[i-1];
for(long long i=1;i<=mid;i++)
{
b[s[i]]-=d[i];
b[t[i]+1]+=d[i];
}
for(long long i=1;i<=n;i++)
{
b[i]+=b[i-1];
if(b[i]<0)
return true;
}
return false;
}
int main()
{
cin>>n>>m;
for(long long i=1;i<=n;i++)
{
cin>>r[i];
}
for(long long i=1;i<=m;i++)
{
cin>>d[i]>>s[i]>>t[i];
}
long long l=1,r=m+1;
while(l<r)
{
long long mid=(l+r)/2;
if(check(mid))
r=mid;
else
l=mid+1;
}
if(r==m+1)
cout<<0<<endl;
else
cout<<-1<<endl<<r<<endl;
return 0;
}