BZOJ4476 送礼物

这道题真是有趣呀。

其实就是一个分数规划问题，用一个二分加log来得去掉分母。

分四种情况讨论

1.lenth > L && num ( max ) > num ( min )

2.lenth > L && num ( max ) < num ( min )

3.lenth == L && num ( max ) > num ( min )

4.lenth == L && num ( max ) < num ( min )

1,2种情况中最大值与最小值一定在选择序列两端，设左右端点编号为i,j

1. ( Vi - Vj ) / ( i - j + k ) = ans -> ( Vi - i * ans ) - ( Vj - j * ans ) = k * ans

二分ans并check左式最大值是否大于右式

2.( Vj - Vi ) / ( i - j + k ) = ans -> ( Vj + j * ans ) - ( Vi + i * ans ) = k * ans

同情况1

3,4用单调队列for一遍就可以了

 #include<cstdio>

 #include<algorithm>

 #include<cassert>

 //#define DEBUG

 using namespace std ; 

 const int MAXN =  *  +  ;

 int N , K , L , R ;

 long long a [ MAXN ] ;

 int p [ MAXN ] ;

 template < class T1 , class T2 >

 void max_equal ( T1 & a , const T2 & b ) {

     if ( a < b ) a = b ;

 }

 double solve1 ( const double M ) {

 #define f(i) (a[i]-M*(i))

     double ans = -1e9 ;

     int l =  , r = - ;

     for ( int i = L ; i <= N ; ++ i ) {

         while ( r - l +  >=  && i - p [ l ] +  > R ) ++ l ;

         while ( r - l +  >=  && ! ( f ( p [ r ] ) < f ( i - L +  ) ) ) -- r ;

         p [ ++ r ] = i - L +  ;

         max_equal ( ans , f ( i ) - f ( p [ l ] ) ) ;

     }

     return ans ;

 #undef f

 }

 double Solve1 () {

     double L =  , R = 1e4 ;

     while ( R - L >= 1e- ) {

         const double M = ( L + R ) /  ;

         if ( solve1 ( M ) >= K * M ) L = M ;

         else R = M ;

     }

     return ( L + R ) /  ;

 }

 double solve2 ( const double M ) {

 #define f(i) (a[i]+M*(i))

     double ans = -1e9 ;

     int l =  , r = - ;

     for ( int i = L ; i <= N ; ++ i ) {

         while ( r - l +  >=  && i - p [ l ] +  > R ) ++ l ;

         while ( r - l +  >=  && ! ( f ( p [ r ] ) > f ( i - L +  ) ) ) -- r ;

         p [ ++ r ] = i - L +  ;

         max_equal ( ans , f ( p [ l ] ) - f ( i ) ) ;

     }

     return ans ;

 #undef f

 }

 double Solve2 () {

     double L =  , R = 1e4 ;

     while ( R - L >= 1e- ) {

         const double M = ( L + R ) /  ;

         if ( solve2 ( M ) >= K * M ) L = M ;

         else R = M ;

     }

     return ( L + R ) /  ;

 }

 double Solve3 () {

     double ans = -1e9;

     int l =  , r = - ;

     for ( int i =  ; i <= N ; ++ i ) {

         while ( r - l +  >=  && i - p [ l ] +  > L ) ++ l ;

         while ( r - l +  >=  && ! ( a [ p [ r ] ] < a [ i ] ) ) -- r ;

         p [ ++ r ] = i ;

         max_equal ( ans , a [ i ] - a [ p [ l ] ] ) ;

     }

     return ans / ( L -  + K ) ;

 }

 double Solve4 () {

     double ans = -1e9;

     int l =  , r = - ;

     for ( int i =  ; i <= N ; ++ i ) {

         while ( r - l +  >=  && i - p [ l ] +  > L ) ++ l ;

         while ( r - l +  >=  && ! ( a [ p [ r ] ] > a [ i ] ) ) -- r ;

         p [ ++ r ] = i ;

         max_equal ( ans , a [ p [ l ] ] - a [ i ] ) ;

     }

     return ans / ( L -  + K ) ;

 }

 double solve () {

     scanf ( "%d%d%d%d" , & N , & K , & L , & R ) ;

     for ( int i =  ; i <= N ; ++ i ) scanf ( "%lld" , & a [ i ] ) ;

     return max ( max ( Solve1 () , Solve2 () ) , max ( Solve3 () , Solve4 () ) ) ;

 }

 int main () {

     int T ;

     scanf ( "%d" , & T ) ;

     while ( T -- ) printf ( "%.4lf\n" , solve () ) ;

     return  ;

 }

巴特西

BZOJ4476 送礼物

最新文章

热门文章