自动搬运

查看原文

来自洛谷，原作者为

	zyq_666_kpzc **

搬运于2025-08-24 22:25:17，当前版本为作者最后更新于2024-07-19 16:52:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

思路分析

根据题意，我们可以知道：比正确答案 $c$ 大的数一定能在规定时间内走完，比正确答案 $c$ 小的数不可能在规定时间内走完，答案 $c$ 具有单调性。

于是，我们可以想到用二分答案解决此题，二分最后的答案 $c$，在合法的范围中求出最小的答案，直接输出。

注意：最后的答案是浮点数！！！

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
const double h=1e-7;
double t,ju_li[1005],su_du[1005],l=10000000,r=10000000;;
bool check(double x){
	double sum=0;
	for(int i=1;i<=n;i++)sum+=ju_li[i]*1.0/(su_du[i]+x);
	return sum>t;
}
signed main(){
	cin>>n>>t;
	for(int i=1;i<=n;i++){
		cin>>ju_li[i]>>su_du[i];
		l=min(l,su_du[i]);
	}
	l=-l;
	while(l+h<r){
		double mid=(l+r)/2;
		if(check(mid)==true)l=mid;
		else r=mid; 
	}
	printf("%.7lf",r);
	return 0;
}