CFR 294 B. Shaass and Bookshelf ( Greedy )

Problem - 294B - Codeforces
題意：
給一堆相同高度的書，用厚度和寬度描述。放書的方法是相放一層豎的，再將剩下的橫放在那層上。橫放的那層寬度總和不得超過下面豎著放的那層厚度總和。求最小厚度總和。
解法：
由於書的厚度只有兩種，因此可以分開枚舉兩種厚度的數各要疊在上面幾本。枚舉後便可以確定是哪些書，因為相同厚度的情況下，放在上面的書一定是寬度小優先。

int N;
vi T, W;

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

vi srtid1, srtid2;
int tsum1, tsum2;

void preprocess(){
    for( int i = 0; i < N; ++i ){
        if( T[ i ] == 1 )
            srtid1.push_back( i ),
            tsum1 += T[ i ];
        else
            srtid2.push_back( i ),
            tsum2 += T[ i ];
    }
    sort( srtid1.begin(), srtid1.end(), [ & ]( int i, int j ){ return W[ i ] < W[ j ]; } );
    sort( srtid2.begin(), srtid2.end(), [ & ]( int i, int j ){ return W[ i ] < W[ j ]; } );
}

void solve(){
    int ans = tsum1 + tsum2;
    for( int i = 0, wsum1 = 0, ts1 = tsum1; i <= srtid1.size(); ++i ){
        for( int j = 0, wsum2 = 0, ts2 = tsum2; j <= srtid2.size(); ++j ){
            if( wsum1 + wsum2 <= ts1 + ts2 )
                upmin( ans, ts1 + ts2 );
            if( j < srtid2.size() )
                wsum2 += W[ srtid2[ j ] ],
                ts2 -= T[ srtid2[ j ] ];
        }
        if( i < srtid1.size() )
            wsum1 += W[ srtid1[ i ] ],
            ts1 -= T[ srtid1[ i ] ];
    }
    cout << ans << endl;
}