Eisen's Blog

© 2024. All rights reserved.

POJ 1018

May 15, 2012

linkedin枚举贪婪
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
/*
 * http://poj.org/problem?id=1012
 * 思路:
 * 遍历所有可能的带宽,在每种带宽下计算 price
 */
struct Device {
    int mi;
    vector<int> bds;
    vector<int> prs;
};

int main() {
    int t, n, mi, bw, pr;
    cin>>t;
    while(t--) {
        cin>>n;
        set<int> bands;
        vector<Device> device;
        while(n--) {
            cin>>mi;
            Device d;
            d.mi = mi;
            while(mi--) {
                cin>>bw>>pr;
                bands.insert(bw);
                d.bds.push_back(bw);
                d.prs.push_back(pr);
            }
            device.push_back(d);
        }
        double bp = 0;
        bool finished;
        for(set<int>::iterator it = bands.begin(); it != bands.end(); ++it) {
            int cur_band = *it, sum = 0;

            for(int i=0; i != device.size(); i++) {
                finished = false;
                int cur_pr = 65535;
                for(int j=0; j != device[i].mi; j++) {
                    if(device[i].bds[j] >= cur_band && device[i].prs[j] < cur_pr) {
                        cur_pr = device[i].prs[j];
                        finished = true;
                    }
                }
                // 如果在某个设备上找不到比 cur_band 更大的设备
                // 说明 cur_band 不能作为最终结果
                // 则不再循环 并采用 bands 中的下一个 band
                if(!finished) break;
                else sum += cur_pr;
            }

            if(!finished) continue;
            if(bp < 1.0 * cur_band / sum) bp = 1.0 * cur_band / sum;
        }

        printf("%.3f\n", bp);
    }
    return 0;
}