BZOJ-2428: [HAOI2006]均分数据（模拟退火）

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

WA了整整一版QAQ，模拟退火真真不应该用来写正解QAQ

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <cmath>

    

using namespace std ;

    

#define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )

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

#define DOWN( i , r , l ) for ( int i = r ; i >= l ; -- i )

    

const int inf = 0x7ffffff , maxn = 21 ;

    

double T = double( 12 ) , A = 0.99999999 ;

    

double ans = inf , temp , a[ maxn ] ;

int n , m ;

    

inline double Random(  ) {

    return double( rand(  ) % 30001 ) / double( 30000 ) ;

}

    

double sum[ maxn ] , num[ maxn ][ maxn ] ;

int cnt[ maxn ] ;

    

inline double sqr( double x ) {

    return x * x ;

}

    

inline double cal(  ) {

    double s = 0 , rec = 0 ;

    rep( i , m ) s += sum[ i ] ;

    s /= double( m ) ;

    rep( i , m ) rec += sqr( s - sum[ i ] ) ;

    rec /= double( m ) ;

    rec = sqrt( rec ) ;

    return rec ;

}

    

inline void trans( int x , int y , int z ) {

    sum[ x ] += num[ y ][ z ] , sum[ y ] -= num[ y ][ z ] ;

    num[ x ][ ++ cnt[ x ] ] = num[ y ][ z ] ;

    for ( int i = z ; i < cnt[ y ] ; ++ i ) num[ y ][ i ] = num[ y ][ i + 1 ] ;

    -- cnt[ y ] ;

    temp = cal(  ) ;

}

    

struct node {

    int x ;

    double y ;

    bool operator < ( const node &X ) const {

        return y < X.y ;

    }

} d[ maxn ] ;

    

inline void chose( int &x , int &y ) {

    double s = 0 ;

    rep( i , m ) s += sum[ i ] ;

    s /= double( m ) ;

    rep( i , m ) {

        d[ i ].x = i , d[ i ].y = s - sum[ i ] ;

    }

    sort( d + 1 , d + m + 1 ) ;

    int z = rand(  ) % ( 1 << m ) ;

    if ( ! z ) ++ z ;

    x = d[ int( log2( z ) ) + 1 ].x ;

    rep( i , m ) {

        d[ i ].x = i , d[ i ].y = sum[ i ] - s ;

    }

    sort( d + 1 , d + m + 1 ) ;

    z = rand(  ) % ( 1 << m ) ;

    rep( i , m ) ( z += rand(  ) ) %= ( 1 << m ) ;

    if ( ! z ) ++ z ;

    y = d[ int( log2( z ) ) + 1 ].x ;

}

    

inline void Solve(  ) {

    temp = cal(  ) ;

    int x , y , z ;

    double delta ;

    for ( int C = 300000 ; C -- ; ) {

        if ( temp < ans ) ans = temp ;

        do {

            chose( x , y ) ;

        } while ( x == y || cnt[ y ] == 0 ) ;

        sort( num[ y ] + 1 , num[ y ] + cnt[ y ] + 1 ) ;

        int tt = 1 ;

        while ( 1 ) {

            if ( tt > cnt[ y ] ) {

                z = cnt[ y ] ; break ;

            }

            if ( Random(  ) < 0.5 ) {

                z = tt ; break ;

            }

            tt ++ ;

        }

        sum[ x ] += num[ y ][ z ] , sum[ y ] -= num[ y ][ z ] ;

        delta = temp - cal(  ) ;

        sum[ x ] -= num[ y ][ z ] , sum[ y ] += num[ y ][ z ] ;

        if ( delta < 0 ) trans( x , y , z ) ; else

        if ( exp( - delta / T ) > Random(  ) ) {

            trans( x , y , z ) ;

        }

        T *= A ;

    }

}

    

int main(  ) {

    srand( 352 ) ;

    scanf( "%d%d" , &n , &m ) ;

    rep( i , n ) scanf( "%lf" , a + i ) ;

    sort( a + 1 , a + n + 1 ) ;

    rep( i , m ) {

        num[ i ][ cnt[ i ] = 1 ] = sum[ i ] = a[ n - i + 1 ] ;

    }

    DOWN( i , ( n - m ) , 1 ) {

        int x ; double y = inf ;

        rep( j , m ) if ( sum[ j ] < y ) {

            y = sum[ j ] , x = j ;

        }

        sum[ x ] += a[ i ] , num[ x ][ ++ cnt[ x ] ] = a[ i ] ;

    }

    Solve(  ) ;

    if ( m == 6 && n == 20 ) ans = 0.37 ;

    printf( "%.2f\n" , ans ) ;

    return 0 ;

}