题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=4952
因为速度越快一定时间越短，所以满足二分性
注意左右边界要开大点…
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include<bits/stdc++.h> #define maxn 1010 #define db double #define eps 1e-9 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } int n,m; int d[maxn],s[maxn]; inline bool check(db mid){ db sum=0; for(int i=1; i<=n; i++){ db v=s[i]*1.0+mid; if(v<=0)return false; sum+=d[i]*1.0/v; } return sum<m*1.0; } int main(){ n=rd(),m=rd(); for(int i=1; i<=n; i++)d[i]=rd(),s[i]=rd(); db l=-1e9,r=1e9; while(r-l>eps){ db mid=(l+r)/2; if(check(mid))r=mid; else l=mid; } printf("%.9lf\n",l); return 0; } |