PKU 1018 Communication System - kusano

帯域幅を変えながら、その帯域幅以上で最安の製品を選んでいく。
#include <iostream>
#include <vector>

using namespace std;

struct MAN
{
    int B, P;
};

int main()
{
    int t;  cin >> t;

    for ( int i=0; i<t; i++ )
    {
        //  読み込み
        int n;  cin >> n;
        vector<vector<MAN> > man( n );

        for ( int j=0; j<n; j++ )
        {
            int m;  cin >> m;
            man[j].resize( m );
            for ( int k=0; k<m; k++ )
                cin >> man[j][k].B >> man[j][k].P;
        }

        //  
        double BP = 0;
        int B = 0;

        while ( true )
        {
            //  帯域幅がBより大きく最安の製品を選ぶ
            vector<MAN> sys( n );
            for ( int i=0; i<n; i++ )
            {
                sys[i].P = INT_MAX;
                for ( int j=0; j<(int)man[i].size(); j++ )
                    if ( man[i][j].B > B  &&
                         man[i][j].P < sys[i].P )
                        sys[i] = man[i][j];
            }

            //  条件を満たす製品が無ければ終了
            bool fail = false;
            for ( int i=0; i<n; i++ )
                if ( sys[i].P == INT_MAX )
                    fail = true;
            if ( fail )
                break;

            //  B/Pを計算
            int b = INT_MAX;
            int p = 0;

            for ( int i=0; i<n; i++ )
                b = min( b, sys[i].B ),
                p += sys[i].P;

            BP = max( BP, (double)b/p );

            //  次は今回の最小帯域幅より大きい製品を試す
            B = b;
        }

        //
        printf( "%.3f\n", BP );
    }

    return 0;
}