BZOJ-2876: [Noi2012]骑行川藏（拉格朗日乘数）

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2876

拉格朗日乘数，然后二分里面再弄个二分或牛顿法解方程。

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

  

using namespace std ;

  

#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

  

const int maxn = 10100 ;

  

typedef long double ld ;

  

const int inf = 1000000000 ;

const ld esp = 0.0000000000000001 , INF = ld( inf ) ;

  

ld s[ maxn ] , k[ maxn ] , v[ maxn ] , e , x[ maxn ] ;

int n ;

  

inline ld sqr( ld ret ) {

    return ret * ret ;

}

  

inline void cal( int i , ld mid ) {

    ld l = v[ i ] , r = INF , md ;

    while ( r - l > esp ) {

        md = ( l + r ) / ld( 2 ) ;

        if ( ( ld( 2 ) * mid * k[ i ] * ( md - v[ i ] ) * sqr( md ) + ld( 1 ) ) > 0 ) {

            l = md ;

        } else r = md ;

    }

    x[ i ] = l ;

}

  

inline bool check( ld mid ) {

    ld sum = 0 ;

    rep( i , n ) {

        cal( i , mid ) ;

        sum += ( k[ i ] * sqr( x[ i ] - v[ i ] ) * s[ i ] ) ;

    }

    return sum <= e ;

}

  

inline ld cal_t( ld lan ) {

    check( lan ) ;

    ld ans = 0 ;

    rep( i , n ) ans += ( s[ i ] / x[ i ] ) ;

    return ans ;

}

  

int main(  ) {

    double temp , a , b , c ;

    scanf( "%d%lf" , &n , &temp ) ; e = temp ;

    rep( i , n ) {

        scanf( "%lf%lf%lf" , &a , &b , &c ) ;

        s[ i ] = a , k[ i ] = b , v[ i ] = c ;

    }

    ld l = - INF, r = 0 , mid ;

    while ( r - l > esp ) {

        mid = ( l + r ) / ld( 2 ) ;

        if ( check( mid ) ) l = mid ; else r = mid ;

    }

    printf( "%.8f\n" , double( cal_t( l ) ) ) ;

    return 0 ;

}