博客

二分练习题

  • Post author:
  • Post category:其他


目录



二分 模板(新)


模板题


找数组中某个数的上下界 

#include <iostream>
#include <string.h>
using namespace std;
const int N=1e5+10;
const int M=1e5+10;

int a[N];
int main() {
	//ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int n,q;scanf("%d%d",&n,&q);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
   
   
    while(q--){
		int x;scanf("%d",&x);

		
		int l=0,r=n-1;
		while(l<r){
			int mid = l+r >>1;//找满足条件的左边界：则往下取
			if(a[mid]>=x)r=mid;//满足的条件：找左边界，则满足区间在右边，右边的大于等于x
			else l=mid+1;
		}
		if(a[l]!=x){cout<<"-1 -1"<<endl;continue;}
		
		
		cout<<l<<" ";
		l=0,r=n-1;
		while(l<r){
			 int mid = 1+l+r >>1;//找右边界：往上取
			 if(a[mid]<=x)l=mid;//此处满足条件：找右边界，则满足区间在左边，左边的小于等于x
			 else r=mid-1;
		}
		cout<<l<<endl;
    }
    return 0;
}

套路总结：



二分习题



洛谷的题单


洛谷二分题单链接



P2249 【深基13.例1】查找

题意：输出某个数在数组中第一次出现的位置，若无则输出-1 

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;

int a[N],n,m;

int bifi(int x)
{
    int l=1,r=n;
    while(l<r)//因为是升序，所以找某个数左边界
    {
        int mid=l+r>>1;
        if(a[mid]>=x)r=mid;
        else l=mid+1;
    }
    return l;
}

int main()
{
    scanf("%d%d",&n,&m);
    
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    
    while(m--)
    {
        int k;scanf("%d",&k);
        
        int pos=bifi(k);
        if(a[pos]==k)printf("%d ",pos);
        else printf("-1 ");
    }
    
    return 0;
}



P1102 A-B 数对

题意：给一数组，和一整数c；在数组中统计满足a-b=c的b的个数；

思路：找数组中某个数的个数 -> 找上下边界 -> 二分。故先排序。

注意：开long long

手写二分： 

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;

int a[N],b[N],n,m;ll ans;

int left(int x)
{
	int l=0 ,r=n-1;
	while(l<r)
	{
		int mid=l+r>>1;
		if(a[mid]>=x)r=mid;
		else l=mid+1;
	}
	return l;
}

int right(int x)
{
	int l=0 ,r=n-1;
	while(l<r)
	{
		int mid=l+r+1>>1;
		if(a[mid]<=x)l=mid;
		else r=mid-1;
	}
	return l;
}


int main()
{
    scanf("%d%d",&n,&m);

    for(int i=0;i<n;i++){scanf("%d",&a[i]);b[i]=a[i]-m;}

    sort(a,a+n);
    sort(b,b+n);

    for(int i=0;i<=n;i++)
	{
		int l=left(b[i]),r=right(b[i]);

		if(a[l]==b[i]&&a[r]==b[i])ans+=r-l+1;

	}
    printf("%lld",ans);
    return 0;
}

用函数找上下界： 

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
typedef pair<int,int> PII;
const int N=2e5+10;

int a[N],b[N],n,m;ll ans;

int main()
{
    scanf("%d%d",&n,&m);

    for(int i=0;i<n;i++){scanf("%d",&a[i]);}

    sort(a,a+n);

    ans=0;
    for(int i=0;i<=n;i++)
	{
		ans+=(upper_bound(a,a+n,a[i]-m)-lower_bound(a,a+n,a[i]-m));

	}
    printf("%lld",ans);
    return 0;
}



P1873 砍树

题意：给一数组表示原来树的高度，给需要树的长度m，设定参数h，砍掉比h高的树的部分，且满足砍下的树的长度总和 >= m；

分析：找满足条件的 h 的最大值 -> h有上下界（【0，最高的树的高度】）且单调增 -> 找满足条件的右边界

-> 满足条件：找右边界，左区间值偏小 ，则 砍下来的总长度 >= m； 

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;

int n,m,a[N];

ll check(int x)
{
	ll sum=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]>x)sum+=a[i]-x;
	}
	return sum>=m;
}
int bifi_r(int l,int r)
{
	int mid;
	while(l<r)
	{
		mid=l+r+1>>1;
		if(check(mid))l=mid;
		else r=mid-1;
	}
}

int main()
{
    cin>>n>>m;

    int mx=0;

    for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		mx=max(mx,a[i]);
	}

	sort(a+1,a+1+n);

	cout<<bifi_r(0,mx)<<endl;;

    return 0;
}



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

题意：求解-100到100之间的三个不同实根

思路：我暴力做的，没想到怎么能用二分QAQ 

#include <bits/stdc++.h>
#define ll long long
using namespace std;

double a,b,c,d;

bool check(double x)
{
	double sum=a*x*x*x+b*x*x+c*x+d;

	if(fabs(sum)<=1e-4)return 1;
	return 0;
}


int main()
{
    scanf("%lf%lf%lf%lf",&a,&b,&c,&d);

    //暴力应该行吧 200*1e5

    int cnt=0;double a[5];
    for(double i=-100.00;i<=100.00;i+=1e-4)
	{
		if(check(i)){a[++cnt]=i;if(cnt==3)break;}
	}

    printf("%.2f %.2f %.2f",a[1],a[2],a[3]);

    return 0;
}



P1678 烦恼的高考志愿


题意：给出 n 个学校录取分数，m 个学生的分数； 学生分数与学校录取分数相差最小的值 为不满意度，求所有学生的不满意度的总和


**

分析：对每个学生分数x 差值最小的值 -> min(大于x的，小于x的) -> 找x的左右边界

** 

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;

int a[N];

int left(int l,int r,int x)
{
	while(l<r)
	{
		int mid =l+r>>1;
		if(a[mid]>=x)r=mid;
		else l=mid+1;
	}//cout<<l<<endl;
	return l;

}

int right(int l,int r,int x)
{
	while(l<r)
	{
		int mid =l+r+1>>1;
		if(a[mid]<=x)l=mid;
		else r=mid-1;
	}//cout<<l<<endl;
	return l;

}

int main()
{
	//分数线从小到大
	//查找比x大和小的数，
	//即找左边界，满足 >=
	//找右边界 ，满足 <=

	int m,n;scanf("%d%d",&m,&n);
	for(int i=0;i<m;i++)scanf("%d",&a[i]);

	sort(a,a+m);

	ll ans=0;
	while(n--)
	{
		int x;scanf("%d",&x);

		int l=left(0,m-1,x);
		int r=right(0,m-1,x);

		ans+=min(abs(a[l]-x),abs(a[r]-x));
	}
	printf("%lld",ans);


    return 0;
}



P2440 木材加工


题意：给 n个木头的长度，以及要求的切割后等长的木头的数量k；要求切割得到等长的木头的数量至少为k，求切割得到的木头的最大长度。


分析：切割木头的最大值 -> 该长度有上下界（【0，最长木头长度】）单增 -> 二分求解，找符合条件的右边界

-> 符合条件：找右边界，左边区间值偏小，则得到的木头个数 >= k；
 

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int N=1e5+10;

int n,k,a[N];

int check(int x)
{
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		cnt+=a[i]/x;
	}
	return cnt>=k;
}

int main()
{
    cin>>n>>k;

    int mx=0;
    for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		mx=max(mx,a[i]);
	}

	int l=0,r=mx,mid;

	while(l<r)//满足的最大长度，右边界
	{
		mid=l+r+1>>1;
		if(check(mid))l=mid;
		else r=mid-1;
	}

	cout<<l<<endl;


    return 0;
}



P2678 [NOIP2015 提高组] 跳石头


题意：给起点到终点的距离 L，起点到终点的石头个数 n 及对应石头距起点的距离 ai，至多要拿走的石头个数 m 。 移走石头使最短跳跃距离尽可能长，求最短跳跃距离的最大值。


分析：求 ···(此处是最短跳跃距离)的最大值 -> 上下界（0，L）且单增 -> 二分找符合条件的右边界



-> 符合条件 ：找右边界，左边的数偏小 则挪走的石头个数 <= m ; （挪走数量，将小于mid的区间挪走一个石头）
 

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;

int L,n,m,a[N];

int check(int x)
{
	int cnt=0,t=0;

	for(int i=1;i<=n+1;i++)
	{
		if(a[i]-a[t]<x)cnt++;
		else t=i;
	}
	return cnt<=m;
}

int bifi_r(int l,int r)
{
	int mid;
	while(l<r)
	{
		mid=l+r+1>>1;
		if(check(mid))l=mid;
		else r=mid-1;
	}
	return l;
}

int main()
{
    cin>>L>>n>>m;

    for(int i=1;i<=n;i++)cin>>a[i];

    a[0]=0;a[n+1]=L;

    cout<<bifi_r(0,L)<<endl;

    return 0;
}



P3853 [TJOI2007]路标设置


题意：给出公路的长度 L ，以及原有路标数量 n 及相应位置 ， 最多可增设路标的数量 k 。 增设路标 使得 相邻路标的最大距离 变小 ，求增设路标后能达到的最小的相邻路标的距离 ；


分析： 求 ····（此处是 相邻路标）的最小值 -> 有上下界（【0，L】）单增 -> 二分找满足条件的左边界

->

满足条件： 左边界则右边的值偏大 ， 若偏大则增设路标数量 <= k ；（ 增设数量等于 大于mid的区间分割成小于等于mid的长度 ，即 cnt + = (a[i]-a[i-1])/mid , if((a[i]-a[i-1])%mid==0)cnt–;）

注意：本题与上一题取石头最大区别在于 他没有起始石头 所以求区间距离使得从 i=2 开始求 （不能设a[0]=0） 

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
typedef pair<int,int> PII;
const int N=1e5+10;
const int mod=998244353;

int L,n,k,a[N];

int check(int x)
{
	int cnt=0;

	for(int i=2;i<=n;i++)
	{
		cnt+=(a[i]-a[i-1])/x;
		if((a[i]-a[i-1])%x==0)cnt--;
	}

	return cnt<=k;
}

int bifi_l(int l,int r)
{
	int mid;
	while(l<r)
	{
		mid=l+r>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	return l;
}


int main()
{
    cin>>L>>n>>k;

    for(int i=1;i<=n;i++)cin>>a[i];

    cout<<bifi_l(0,L)<<endl;

    return 0;
}



P1182 数列分段 Section II


题意：给 n 个正整数的集合，要求分成 m 段 (连续) ，求每段和的最大值的最小。最大值最小的定义：并且无论如何分段，最大值不会小于这个值。


分析：求···（此处 每段和的最大值）的最小值 -> 有上下界（【集合中的最小值，集合最大值的m倍】）-> 二分找满足条件的左边界

-> 满足条件 ：找左边界，右边区间值偏大，则 所有区间和等于mid的个数小于等于 m
 

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
typedef pair<int,int> PII;
const int N=1e5+10;
const int mod=998244353;

int n,m,a[N];

bool check(int x)
{
	int sum=0,cnt=1;//cnt初始化为一是因为 下面的循环最后有一组未被计入 ！！！！因为这个初始化搞了好久

	for(int i=1;i<=n;i++)
	{
		if(sum+a[i]>x)sum=a[i],cnt++;
		else sum+=a[i];
	}
	return cnt<=m;
}

int bifi_l(int l,int r)
{
	while(l<r)
	{
		int mid=(l+r)/2;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	return l;
}

int main()
{
	cin>>n>>m;

	int l=0,r=0; a[0]=0;

	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		l=max(l,a[i]);
		r+=a[i];
	}

	cout<<bifi_l(l,r)<<endl;

	return 0;
}



P1163 银行贷款


题意：给定要还的债总金额 n ， 每月要还金额 m ，要还的月数 k ，求利率 x ；


分析： 利率 x 有上下界 -> 一般是0 – 1.0(但是这个题有一个测试点 大于2小于3) -> 二分找（上下界都行）-> 找左边界吧 -> 则右边区间偏大 ， 则还钱还多了


难点在于我不会这个什么利率什么的

去查询了才知道怎么做：设利率为x (十进制的) , 则最后输出百分数时要乘上100

首先 要清楚 ：(1+x) * 本金(ni) = 每月要还的金额m ;

其次 注意“假设利率按月累计” 指假如第一个月的利率为(1+p)，那么第二个月就变成了(1+p)(1+p)

所以最后 对于枚举的x 有这么个式子

在这里插入图片描述

我的check()用了等比求和公式，也可以直接for(1->k)sum+=m/pow(1+x,i); 

#include <bits/stdc++.h>
using namespace std;

double  n,m;int k;

bool check(double x)
{
	return pow(1.0/(1+x),k) >= 1-n/m*x;
}

double bifi_l(double l,double r)
{
	double mid;
	while(r-l>1e-4)
	{
		double mid=(l+r)/2;
		if(check(mid))r=mid;
		else l=mid;
	}
	return l;
}


int main()
{
	cin>>n>>m>>k;

	printf("%.1f\n",bifi_l(0.0,5.0)*100);

	return 0;
}



P3743 kotori的设备

本题还差两个测，以后再补 

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
typedef pair<int,int> PII;
const int N=1e5+10;

int n,q,a[N],b[N];

int ck()
{
	int k=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]==0)k++;
	}
	if(k>=n-1)return 1;
	return 0;
}

int check(double x)
{
	double sum=0;
	for(int i=1;i<=n;i++)
	{
		double t=(double)b[i]-x*a[i];
		if(t<=0)sum+=fabs(t);
	}
	return q*x-sum>0;
}

double bifi_r(double  l,double  r)
{
	double mid;

	while(r-l>1e-6)
	{
		mid=(l+r)/2;
		if(check(mid))l=mid;
		else r=mid;
	}
	return l;
}

int main()
{
	cin>>n>>q;



	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
	}

    if(n==1||(n!=1&&ck())){cout<<-1<<endl;return 0;}

	printf("%.10f\n",bifi_r(0,inf));

	return 0;
}

//题意：给n设备的 每秒耗能ai 和原有能量bi ，以及 充电宝每秒可供及的能量 p。
//求最多能共同使用这些设备多久（直至有能量降为0），若可以一直使用 ，则输出-1.

//特殊情况：只有一个的时候 ， 或者 全都不消耗 ，或者 只有一个耗能其余不耗

//求使用时间最大值 -> 有上下界（【0,】） -> 找右边界，左边区域的时间偏小，即全部都没变成0；


版权声明：本文为weixin_52723996原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。