CFR 416 C. Booking System ( Greedy )

Problem - 416C - Codeforces
題意：
給一堆客人的要求，用人數和獲益描述，接著給一些桌子其容量。每個桌子只能招待一組客人的要求，而某個桌子可以招待一組客人若且唯若其容量不小於人數，此時若選擇配對則獲得該獲益。求最大總獲益，並輸出對應配對。
解法：
考慮由當前最大獲益的要求開始滿足，總是將該組放到可容的最小桌子。試反證這樣是錯的，那麼代表該桌子寧願塞另一個收益更小的客人而放棄這組，顯然不合理，故貪心法正確。

int N;
vi C, P;
int K;
vi R;

void init(){
    cin >> N;
    C = P = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> C[ i ] >> P[ i ];
    cin >> K;
    R = vi( K );
    for( int i = 0; i < K; ++i )
        cin >> R[ i ];
}

typedef tuple< int, int, int > tiii;
vector< tiii > request;

void preprocess(){
    for( int i = 0; i < N; ++i )
        request.emplace_back( P[ i ], C[ i ], i );
    sort( request.begin(), request.end(), greater< tiii >() );
}

void solve(){
    int profit = 0;
    vp acreq;
    vi vis( K );
    for( int i = 0; i < N; ++i ){
        int val, size, id;
        tie( val, size, id ) = request[ i ];
        int tsz = INF, tid = -1;
        for( int j = 0; j < K; ++j )
            if( not vis[ j ] and R[ j ] >= size )
                if( upmin( tsz, R[ j ] ) )
                    tid = j;
        if( tid == -1 )
            continue;
        profit += val;
        vis[ tid ] = 1;
        acreq.push_back( pii( id, tid ) );
    }
    cout << ( int ) acreq.size() << " " << profit << endl;
    for( int i = 0; i < acreq.size(); ++i )
        cout << acreq[ i ].first + 1 << " " << acreq[ i ].second + 1 << endl;
}