自动搬运

查看原文

来自洛谷，原作者为

	qq1010903229 嘻嘻嘻

搬运于2025-08-24 21:52:15，当前版本为作者最后更新于2018-04-16 13:21:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题使用二分答案。

在验证一个使用时间时，若设备已有的能量大于使用时间需要的能量，忽略该设备。

否则用充电器充电，使设备已有的能量等于使用时间需要的能量，并记录需要的能量。

最后比较需要的能量总和和充电器最多提供的能量。

-1特判：

若所有设备的消耗能量速度总和还是小于充电器的充电速度，输出-1。

AC代码如下：

#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;
}