洛谷二分题单和二分算法

sixsix666 / 2024-02-01 / 原文

在题目有出现极值的时候可以运用二分算法，像最小值最大化和最大值最小化又或者像会有中位数，大于这个数的时候可以把他全部视为1小于这个数可以全部视为0，这样隐藏的单调也是可以运用二分。最难的好像就是check函数的设计

板子的不同会导致L，R和mid的关系不然会超时，L+1<R的L是=mid,而L<=R的是L=mid+1

1：查找

好像没东西说，就是没找到输出-1可以通过a【r】==x来判断是否输出-1

2.A-B数对

在判断A-B=C这一过程可以变为A-C=B这个式子更加简单便捷，然后因为这是一个查找有多少个数子满足的，所以需要有两个check函数一个获取第一个另一个来获取第二个最后相减这样就对if条件判断当取等的时候是L=mid还是R=mid

另一个方法是运用lower_bound/upper_bound；

lower_bound：lower_bound(a,a+n,x)-a这样就可以满足返回值i是最小的下标i满足ai>=x

upper_bound：upper_bound(a,a+n,x)-a返回值i满足最小ai>x

注意的是这两个需要减去数组名a

3：砍树

没东西特别啊

4：一元三次方程求解

题目这句话是解题的突破点：根与根之差的绝对值

if(sit[i]-size<=m)
		{
			size=sit[i];//成立则移动比较位置，比较下一组
		}
		else
		{
			size=size+m;//设置新的路标，前一个路标已满足，移动位置到新路标
			i--;//防止因为循环把之前的路标给移走了！
			y--;//减少可用新路标数
		}

九：数列分段

关键点是能加则加不能加就不加；

十：银行贷款

还是对精度的控制还有还钱的过程需要考虑

for (int i = 0; i < c; ++i)//模拟还钱过程。
            w = w - b + w * (mid / 100);

十一：设备

当时不会做大概是因为不懂对充电宝的能量怎么处理不懂到底什么时候给谁充多久的电后面看题解发现只要满足所有所需的电量和充电宝的电量关系就可以了。看代码吧还更好懂

#include  <iostream>
using namespace std;
int n;//设备数量
double p;//充电器的充电速度
double a[200000],b[200000];
double lbound=0,rbound=1e10;
double sum=0; //需要的能量总和（验证答案时）、所有设备的消耗能量速度总和（-1特判时）
int check(double ans){//验证答案
	double q=p*ans;//充电器最多提供的能量
	sum=0;
	for(int i=0;i<n;i++){
		if(a[i]*ans<=b[i]){//若设备已有的能量大于使用时间需要的能量
			continue;//忽略该设备
		}
		sum+=(a[i]*ans-b[i]);//否则用充电器充电，使设备已有的能量等于使用时间需要的能量，并记录需要的能量。
	}
	return sum<=q;//最后比较需要的能量总和和充电器最多提供的能量。
}
int main(){
	cin>>n>>p;
	for(int i=0;i<n;i++){
		cin>>a[i]>>b[i];
		sum+=a[i];
	}
	if(sum<=p){//若所有设备的消耗能量速度总和还是小于充电器的充电速度，输出-1。
		cout<<-1.000000<<endl;
		return 0;
	}
	while(rbound-lbound>1e-6){
		double mid=(lbound+rbound)/2;
		if(check(mid)){
			lbound=mid;
			
		}else{
			rbound=mid;
			
		}
	}
	cout<<lbound<<endl;
	return 0;
}