Luogu P2179. [NOI2012] Cycling in Sichuan and Tibet

Original link: https://www.shuizilong.com/house/archives/luogu-p2179-noi2012-%E9%AA%91%E8%A1%8C%E5%B7%9D%E8%97%8F/

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

In the case of the optimal solution, the derivative of each component is the same, and the derivative can be divided into two.

  
   
#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]*(vu[i])*(vu[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);  
   
}  
   

This article is reproduced from: https://www.shuizilong.com/house/archives/luogu-p2179-noi2012-%E9%AA%91%E8%A1%8C%E5%B7%9D%E8%97%8F/
This site is only for collection, and the copyright belongs to the original author.