BZOJ2876 NOI2012 骑行川藏 拉格朗日乘子法+二分法

#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 1e8
#define eps 1e-12

const int MAXN=10000+2;
int N;
double E,s[MAXN],k[MAXN],v[MAXN],x[MAXN],ans;

double Calc(double t){
    double ret=0;
    for(int i=1;i<=N;i++){
        double l=0,r=INF,m;
        while(r-l>eps){
            m=(l+r)/2;
            if(2*t*k[i]*m*m*(m-v[i])>1) r=m;
            else l=m;
        }
        x[i]=(l+r)/2,ret+=k[i]*(x[i]-v[i])*(x[i]-v[i])*s[i];
    }
    return ret;
}

int main(){
    scanf("%d %lf",&N,&E);
    for(int i=1;i<=N;i++) scanf("%lf %lf %lf",s+i,k+i,v+i);

    double l=0,r=INF,m;
    while(r-l>eps){
        m=(l+r)/2;
        if(Calc(m)>=E) l=m;
        else r=m;
    }

    for(int i=1;i<=N;i++) ans+=s[i]/x[i];
    printf("%.8lf\n",ans);

    return 0;
}