注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

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

2014-06-24 18:11:00|  分类: oi,bzoj,拉格朗日 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目: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 ;

  • }



  评论这张
 
阅读(6)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017