学步园

这道题的做法很多，有DP，贪心，二分等，这里用的是枚举，还是Sayeter教我怎么做的呢~

首先找出最终确定的B的取值范围，那么左端点应该是所有设备可选的选择中最小的B里面的最小的lB，右端点应该是可选的最大的B里面的最小的rB。

然后，从左端点枚举到右端点。每一次枚举mB（lb <= mB <= rB），这个枚举mB一定小于或等于这一次的整个设备最终可能选到最小Btmp。对于每一个设备，只需选取大于枚举B的选项里，P最小的那个（这样保证了这次的Ptmp最小）。

对于每一个Btmp / Ptmp比率Rtmp，如果大于当前的ans，则更新即可。枚举结束后即可得到最大的R。

为了方便选B的范围和P，对于每一个设备的可选项，我排了两次序，一次优先B，一次优先P。

最后，注意输出double型数据时，如果交GCC，要用%f，这里被坑了。。

AC代码：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#define INF 1e+10

using namespace std;

int t, n;

struct info
{
        int b, p;
} d[100][100];

int len[100];
int i, j;
double ans, rtmp;
int lb, rb, mb;
int btmp, ptmp;

int cmp_b(const void *x, const void *y)
{
        if ((*(info *)x).b == (*(info *)y).b)
                return (*(info *)x).p - (*(info *)y).p;
        else
                return (*(info *)x).b - (*(info *)y).b;
}

int cmp_p(const void *x, const void *y)
{
        if ((*(info *)x).p == (*(info *)y).p)
                return (*(info *)x).b - (*(info *)y).b;
        else
                return (*(info *)x).p - (*(info *)y).p;
}

int main()
{
        #ifdef BellWind
                freopen("1018.in", "r", stdin);
        #endif // BellWind

        while (~scanf("%d", &t))
        {
                while (t--)
                {
                        scanf("%d", &n);
                        ans = 0;

                        for (i = 0; i < n; i++)
                        {
                                scanf("%d", &len[i]);
                                for (j = 0; j < len[i]; j++)
                                {
                                        scanf("%d%d", &d[i][j].b, &d[i][j].p);
                                }
                                qsort(d[i], len[i], sizeof(d[i][0]), cmp_b);
                        }
//
//                        printf("按行序输出排序后的B/P信息:\n");
//                        for (i = 0; i < n; i++)
//                        {
//                                for (j = 0; j < len[i]; j++)
//                                        printf(".%4d %4d   ", d[i][j].b, d[i][j].p);
//                                printf("\n");
//                        }
//                        printf("\n");

                        rb = lb = INF;

                        for (i = 0; i < n; i++)
                        {
                                if (rb > d[i][len[i]-1].b) {rb = d[i][len[i]-1].b;}
                                if (lb > d[i][0].b) {lb = d[i][0].b;}
//                                printf("$$%4d %4d\n", lb, rb);
                        }
//                        printf("\n");

//                        printf("输出B区间左右端点:\n");
//                        printf("%4d %4d\n\n", lb, rb);

                        for (i = 0; i < n; i++) {qsort(d[i], len[i], sizeof(d[i][0]), cmp_p);}

                        for (mb = lb; mb <= rb; mb++)
                        {
                                btmp = rb;
                                ptmp = 0;

                                for (i = 0; i < n; i++)
                                {
                                        for (j = 0; j < len[i]; j++)
                                        {
                                                if (mb <= d[i][j].b)
                                                {
                                                        ptmp += d[i][j].p;
//                                                        printf("+%4d %4d  ", d[i][j].p, ptmp);
                                                        if (btmp > d[i][j].b)
                                                        {btmp = d[i][j].b;}
                                                        break;
                                                }
                                        }
//                                        printf("#%4d\n", btmp);
                                }
                                rtmp = btmp*1.0 / ptmp*1.0;
//                                printf("**%4d %8.3lf %4d %4d\n\n", mb, rtmp, btmp, ptmp);
                                if (ans < rtmp ) ans = rtmp;
                        }
                        printf("%.3f\n", ans);
                }
        }

        return 0;
}