POJ 1018 Communication System（枚舉）

這道題的做法很多，有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;
}