标签：二分 专题 cout int mid 1000000 long check
二分最重要的就是check函数的编写以及边界的控制
1.一定区间的完全平方数个数（除二分以外的简单写法）
查看代码
cout << (int)(floor(sqrt(b)) - ceil(sqrt(a)) + 1) << endl;
2.跳石头（为了最大化最小间隙，通过二分跳跃距离，期间通过和撤走石头数量进行比较，来判断此距离是否过短或过长）
查看代码
bool check(int x)
{
int sum=0,shi=0;
for(int i=1;i<=n;i++)
{
if(a[i]-shi<x)sum++;
else shi=a[i];
}
if(sum>m)return 0;
return 1;
}
3.Greedy Gift Takers（此题有一个先决条件，如果第x只牛吃不到，那么后面的n-x只都吃不到）
查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,ma;
int l=0,r=0;
int a[1000000],b[1000000];
int check(int x)//判断x是否能吃到滴牛牛
{
for(int i=1;i<=x-1;i++)b[i]=a[i];
sort(b+1,b+x);//排序便于一个接一个的顺序插入
int bu=n-x;
for(int i=1;i<=x-1;i++)
{
if(b[i]<=bu)bu++;//如果x前面的牛牛都会插入到x后面，就继续
else return 0;//如果有一个不行就完damn
}
return 1;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
int p=0;
r=n+1;
while(l+1<r)
{
int mid=l+r>>1;
if(check(mid))l=mid;
else r=mid;
}
cout<<n-l<<endl;
return 0;
}
4.借教室（循环记录借出还入情况绝对会爆，所以采取前缀和的方式来记录）
查看代码
#include <bits/stdc++.h>
#define int long long
#define PII pair<int,int>
using namespace std;
int n,m,k,ans,l,r;
int a[1000000],b[1000000],s[1000000],t[1000000],c[1000000],f[1000000];
vector<PII>v;
bool check(int x)
{
memset(f,0,sizeof f);
for(int i=1;i<=x;i++)//把前面的需求和返还情况都总结出来
{
f[s[i]]+=b[i];
f[t[i]+1]-=b[i];
}
//原理就是用前缀和来看当天的教室借出返还情况，再进行比较
for(int i=1;i<=n;i++)
{
c[i]=c[i-1]+f[i];//在第i天教室的需求情况
if(a[i]<c[i])return 0;
}
return 1;
}
signed main() {
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=m;i++)
{
cin>>b[i]>>s[i]>>t[i];
}
r=m,l=1;
if(check(m))
{
cout<<0;
return 0;
}
while(l<r)
{
int mid=l+r>>1;
if(check(mid))l=mid+1;
else r=mid;
}
cout<<-1<<endl;
cout<<l<<endl;
return 0;
}
5.K-th Number（如果第m大的数为mid，则包含mid的且mid在其中小于第k大的数的子数组数量应该小于m，若大于就是mid取小了）
查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,m;
int a[1000000],b[1000000];
bool check(int mid)
{
memset(b,0,sizeof b);
int sum=0,t=0;
for(int i=1;i<=n;i++)b[i]=b[i-1]+(a[i]>=mid);//前缀和求当前位置比mid大于等于的数量
for(int i=k;i<=n;i++)
{
while(b[i]-b[t]>=k)t++;//固定后端，移动前端的方法算后端为b[i]时满足条件的子数组数量
sum+=t;//t不清除因为b[i]只会越来越大
}
return sum>=m;//大于等于说明mid取小了
}
signed main()
{
int T;
cin>>T;
while(T--)
{
cin>>n>>k>>m;
int l=0,r=0;
for(int i=1;i<=n;i++)cin>>a[i],r=max(a[i],r);
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid))l=mid;
else r=mid-1;
}
cout<<r<<endl;
}
}
标签：二分,
专题,
cout,
int,
mid,
1000000,
long,
check
From： https://www.cnblogs.com/violet-hty/p/18301757