带精度问题的二分的方法
Voltage Keepsake CodeForces - 801C （思维+二分）
本博以这题为原型，分析两种常用的带精度问题的二分方法
第一种，常见二分模型：
while(r-l>eps) { mid=(r+l)/2.00000; if(check(mid)) { l=mid; ans=l; }else { r=mid-eps; } }
用这种模型的话，首先要根据题目确定出正确的eps，然后注意要在checkmid值后，如果满足条件，用一个double ans的额外变量被存储每一次符合条件的值，到最后我们要找的答案就是ans，
然后注意二分的用法，L每一次赋值为mid，而R每一次要赋值为mid-eps，如果不减去eps，有时候这个while二分会进入一个死循环。
第二种模型，对精度问题就好解决，
for(int i=1;i<=200;i++) { mid=(r+l)/2.00000; if(check(mid)) { l=mid; ans=l; }else { r=mid; } }
根据题目数据来直接敲定一共最多二分多少次，根据精度到多少位或者二分的上届最大值，
一般默认二分100次和200次就空可以满足题目的精度和边界问题，
具体为什么可以满足，我们可以这样思考，如果上届很大，也不会比2^200次方大吧，如果精度要求很高，那么1/eps （即eps的倒数，如果要求1e-5的精度，就是1e5）也不会比2^200大
亲测上边界位1e10，精度位1e-4的题目可以用50次就AC，
附上上面那个题目的两种代码
第一种:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb std::ios::sync_with_stdio(false) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define gg(x) getInt(&x) #define eps 1e-6 using namespace std; typedef long long ll; inline void getInt(int* p); const int maxn=1000010; const int inf=0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ struct node { int h; int x; }a[maxn]; int n,p; bool check(double mid) { double need=0.0000; double sum=0.00000; repd(i,1,n) { need=mid*a[i].x-a[i].h; if(need>0.0000000) { sum+=need; }else { } } return 1.000000*mid*p-sum>0.000000; } int main() { gg(n),gg(p); ll sum=0ll; repd(i,1,n) { gg(a[i].x); gg(a[i].h); sum+=(1ll*a[i].x); } if(sum<=p) { printf("-1\n"); }else { double l=0.0000; double r=1e10; double mid; double ans; while(r-l>eps) { mid=(r+l)/2.00000; if(check(mid)) { l=mid; ans=l; }else { r=mid-eps; } } printf("%.5lf\n", ans); } return 0; } inline void getInt(int* p) { char ch; do { ch = getchar(); } while (ch == ' ' || ch == '\n'); if (ch == '-') { *p = -(getchar() - '0'); while ((ch = getchar()) >= '0' && ch <= '9') { *p = *p * 10 - ch + '0'; } } else { *p = ch - '0'; while ((ch = getchar()) >= '0' && ch <= '9') { *p = *p * 10 + ch - '0'; } } }
第二种：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb std::ios::sync_with_stdio(false) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define gg(x) getInt(&x) #define eps 1e-6 using namespace std; typedef long long ll; inline void getInt(int* p); const int maxn=1000010; const int inf=0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ struct node { int h; int x; }a[maxn]; int n,p; bool check(double mid) { double need=0.0000; double sum=0.00000; repd(i,1,n) { need=mid*a[i].x-a[i].h; if(need>0.0000000) { sum+=need; }else { } } return 1.000000*mid*p-sum>0.000000; } int main() { gg(n),gg(p); ll sum=0ll; repd(i,1,n) { gg(a[i].x); gg(a[i].h); sum+=(1ll*a[i].x); } if(sum<=p) { printf("-1\n"); }else { double l=0.0000; double r=1e10; double mid; double ans; for(int i=1;i<=200;i++) { mid=(r+l)/2.00000; if(check(mid)) { l=mid; ans=l; }else { r=mid; } } printf("%.5lf\n", ans); } return 0; } inline void getInt(int* p) { char ch; do { ch = getchar(); } while (ch == ' ' || ch == '\n'); if (ch == '-') { *p = -(getchar() - '0'); while ((ch = getchar()) >= '0' && ch <= '9') { *p = *p * 10 - ch + '0'; } } else { *p = ch - '0'; while ((ch = getchar()) >= '0' && ch <= '9') { *p = *p * 10 + ch - '0'; } } }
投递阿里巴巴等公司10个岗位