• https://www.luogu.com.cn/problem/P2179

最优解情况下每个分量的导数相同，二分这个导数即可。

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(1e4) + 9;
int n;
double e, s[N], k[N], u[N];

double calcV(double x, int i) {
    double l = 0, r = INF, mid;
    int cnt = 233;
    while(cnt--) {
        mid = (l+r)/2;
        if(2*k[i]*s[i]*mid*mid*(mid-u[i])*x > -s[i]) l = mid ;else r = mid;
    }
    return (l+r)/2;
}

double calcE(double x) {
    double res = 0;
    REP(i, n) {
        double v = calcV(x, i);
        res += k[i]*(v-u[i])*(v-u[i])*s[i];
    }
    return res;
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(n);
    RF(e);
    REP(i, n) RF(s[i], k[i], u[i]);
    double l = -INF, r = 0, mid;
    DO(100){
        mid = (l+r)/2;
        if(calcE(mid) <= e) l = mid ;else r = mid;
    }
    mid = (l+r)/2;
    double ans = 0;
    REP(i, n) ans += s[i] / calcV(mid, i);
    printf("%.6lf", ans);
}

Posted by xiaodao
Category: 日常