【bzoj4952】[Wf2017]Need for Speed 二分
题目描述
已知$\sum\limits_{i=1}^n\frac{d_i}{s_i+c}=t$，求$c$ $(d_i>0,s_i+c>0)$输入
第一行包含两个整数n(1≤n≤1000)和t(1≤t≤10^6),分别表示Sheila的行程段数和总时间。 接下来n行,每行描述了Sheila的一段行程。 第i行包含两个整数di(1≤di≤1000)和si(|si|≤1000),分别表示第 i 段行程的距离和表盘读数。 时间单位是小时,距离单位是英里,速度单位是英里每小时。输出
输出常数c,其单位是英里每小时。你的答案绝对或相对误差应该小于10^-6。样例输入
3 5
4 -1
4 0
10 3
样例输出
3.000000000
题解
二分
由于给出的函数是单调的，因此可以直接二分c的取值并判断即可。
注意精度问题，最好使用long double并进行固定100次二分迭代。
#include
#include
using namespace std;
typedef long double ld;
ld d[1010] , s[1010];
int main()
{int n , i , cnt = 100;ld t , l = 1e18 , r = 1e18 , mid , ret;scanf("%d%Lf" , &n , &t);for(i = 1 ; i <= n ; i ++ ) scanf("%Lf%Lf" , &d[i] , &s[i]) , l = min(l , s[i]);l = -l;while(cnt -- ){mid = (l + r) / 2 , ret = 0;for(i = 1 ; i <= n ; i ++ ) ret += d[i] / (s[i] + mid);if(ret < t) r = mid;else l = mid;}printf("%.9Lf\n" , l);return 0;
}
转载于:https://www.cnblogs.com/GXZlegend/p/7598875.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！