CFR 557 C. Arthur and Table ( DP )

Problem - 557C - Codeforces
題意：
一個桌子有若干個腳，每個腳用其高度和拔掉該腳所需花費描述。求最小總花費，使得最常的腳是絕對多數( 過所有腳數量一半 )。
解法：
利用各種預處理。枚舉最大長度後，透過各種前綴和快速得到更大長度的花費總和，接著枚舉花費，透過預處理快速得到拔除所需拔除的較小長度腳之最小總花費。

const int MAXL = ( int ) 1e5;
const int MAXD = 200;

int N;
vi L;
vi D;

void init(){
    cin >> N;
    L = D = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> L[ i ];
    for( int i = 0; i < N; ++i )
        cin >> D[ i ];
}

vp ld; // pii( L, D )
vi lcnt; // count of L
vi plcnt; // prefix sum of count of L, [ 1, L )
vvi _d_l_cnt; // count of ( L, D )
vvi p_d_l_cnt; // under fixed D, prefix sum of count of L, [ D ][ 1, L )

void preprocess(){
    ld = vp( N );
    for( int i = 0; i < N; ++i )
        ld[ i ] = pii( L[ i ], D[ i ] );
    sort( ld.begin(), ld.end() );
    lcnt = vi( MAXL + 1 );
    for( int i = 0; i < N; ++i )
        ++lcnt[ L[ i ] ];
    plcnt = vi( MAXL + 1 );
    for( int i = 0; i < MAXL; ++i )
        plcnt[ i + 1 ] = plcnt[ i ] + lcnt[ i ];
    _d_l_cnt = vvi( MAXD + 1, vi( MAXL + 1 ) );
    for( int i = 0; i < N; ++i )
        ++_d_l_cnt[ D[ i ] ][ L[ i ] ];
    p_d_l_cnt = vvi( MAXD + 1, vi( MAXL + 1 ) );
    for( int i = 1; i <= MAXD; ++i )
        for( int j = 0; j < MAXL; ++j )
            p_d_l_cnt[ i ][ j + 1 ] = p_d_l_cnt[ i ][ j ] + _d_l_cnt[ i ][ j ];
}

void solve(){
    int ans = INF;
    for( int i = N - 1, ds = 0; 0 <= i; ds += ld[ i ].second, --i ){ // ds : sum of D for larger Ls
        if( i + 1 < N and ld[ i ].first == ld[ i + 1 ].second ) // if same L, then it had been considered, thus skip
            continue;
        int chcnt = 0, cost = 0, rmgol = max( 0, plcnt[ ld[ i ].first ] - ( lcnt[ ld[ i ].first ] - 1 ) ); // remove goal = count of smaller - ( count of cur - 1 )
        for( int j = 1; j <= MAXD; ++j ){
            chcnt += p_d_l_cnt[ j ][ ld[ i ].first ];
            cost += p_d_l_cnt[ j ][ ld[ i ].first ] * j;
            if( chcnt >= rmgol ){
                cost -= ( chcnt - rmgol ) * j;
                chcnt = rmgol;
                break;
            }
        }
        if( chcnt == rmgol )
            upmin( ans, cost + ds );
    }
    cout << ans << endl;
}