p1018.cpp

大概POJ上50道比较难的题的代码

#include <iostream>
using namespace std;
int main(){
    int N;
    cin >> N;
    while(N--){
        int a[110][110][2],g[110];
        int n;
        cin >> n;
        for(int i = 0;i < n;++i){
            cin >> g[i];
            for(int j = 0;j < g[i];++j) cin >> a[i][j][0] >> a[i][j][1];
        }
        double res(0.0);
        int ans;
        for(int i = 0;i < n;++i)
          for(int ii = 0;ii < g[i];++ii){
            int x = a[i][ii][0],j;
            ans = a[i][ii][1];
            for(j = 0;j < n;++j)
              if(j != i){
                int t,minp(-1);
                for(t = 0;t < g[j];++t)
                    if(a[j][t][0] >= x && (minp > a[j][t][1] || minp == -1)) minp = a[j][t][1];
                if(minp == -1) break;
                else ans += minp;
              }
            if(j == n && double(x) / ans > res){ 
                res = double(x) / ans;
            }
        }
        printf("%.3lf\n",res);
    }
}