POJ 1018

#include<iostream>
#define MAXN 105
#define inf 10000000
#include<vector>
#include<iomanip>
#include<algorithm>

using namespace std;

struct node
{
    double b;
    double p;
};

vector<double> coll;

node _m[MAXN][MAXN];
int size[MAXN];
int n;
void sort_f();
int main()
{
    //freopen("acm.acm","r",stdin);
    int i;
    int j;
    int k;
    double min;
    int test;
    double sum;
    double max;
    double temp;
    bool boo;
    cin>>test;
    while(test --)
    {
        boo = false;
        sum = 0;
        max = -1;
        cin>>n;
        for(i = 0; i < n; ++ i)
        {
            cin>>size[i];
            for(j = 0; j < size[i]; ++ j)
            {
                cin>>_m[i][j].b>>_m[i][j].p;
                coll.push_back(_m[i][j].b);
            }
        }
        sort(coll.begin(),coll.end());
        sort_f();
        for(k = 0; k < coll.size(); ++ k)
        {
            if(k > 0 && coll[k] == coll[k-1])
                continue;
            sum = 0;
            for(i = 0; i < n; ++ i)
            {
                min = inf;
                boo = false;
                for(j = 0; j < size[i]; ++ j)
                {
                    if(_m[i][j].b >= coll[k])
                    {
                        if(_m[i][j].p < min)
                            min = _m[i][j].p;
                        boo = true;
                    }
                    else
                        break;
                }
                if(boo == false)
                {
                    sum = 0;
                    break;
                }
                sum += min;
            }
            if(!boo)
                break;
            if( (temp = double(coll[k]/sum)) > max)
            {
                max = temp;
                //cout<<max<<endl
            }
            
        }
        cout<<setiosflags(ios::fixed)<<setprecision(3)<<max<<endl;
        coll.clear();
    }
}

void sort_f()
{
    int i;
    int j;
    int k;
    for(i = 0; i < n; ++ i)
    {
        for(j = 0; j < size[i]; ++ j)
        {
            for(k = j+1; k < size[i]; ++ k)
            {
                if(_m[i][k].b > _m[i][j].b)
                {
                    iter_swap(&_m[i][k].b,&_m[i][j].b);
                    iter_swap(&_m[i][k].p,&_m[i][j].p);
                }
            }
        }
    }
}

POJ 1018

原文：http://www.cnblogs.com/gavinsp/p/4563211.html