PKU-1018:Communication System

keyword

BruteForce　C++

問題概要

N(<100)個のデバイスがある。それぞれのデバイスはM(<100)個の中からオプションを一つ選ぶ。各オプションはバンド幅bとコストpを持つ。バンド幅の最小値Bとコストの総和Pに対してB/Pを最大化する問題。

解法

Bについて全探索する。データ構造を工夫してBを決めたらB/Pの最大値をO(N * log M)で計算できる様にする。全体の計算量はO(N^2*M*log M)。

#include <cstdio>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

vector<int> bs[110], ps[110];
map<int,int> dict[110];
int N;

double check(int limit){
    int total=0;
    for(int i=0; i<N; i++){
        total += dict[i].lower_bound(limit)->second;
    }
    return (double)limit/total;
}

double solve(){
    for(int i=0; i<N; i++){
        dict[i].clear();
        for(int j=0; j<bs[i].size(); j++){
            if(dict[i].find(bs[i][j])==dict[i].end() || dict[i][bs[i][j]] > ps[i][j]){
                dict[i][bs[i][j]] = ps[i][j];
            }
        }
    }

    for(int i=0; i<N; i++){
        int tmp = 1<<30;
        for(map<int,int>::reverse_iterator itr=dict[i].rbegin(); itr!=dict[i].rend(); itr++){
            tmp = min(tmp, itr->second);
            itr->second = tmp;
        }
    }

    set<int> limits;
    for(int i=0;i<N;i++){
        for(map<int,int>::iterator itr=dict[i].begin(); itr!=dict[i].end(); itr++){
            int limit = itr->first;
            bool ok = true;
            for(int j=0; j<N; j++)if(dict[j].rbegin()->first < limit) ok = false;
            if(ok) limits.insert(limit);
        }
    }

    double ret = 0;
    for(set<int>::iterator itr=limits.begin(); itr!=limits.end(); itr++)
            ret = max(ret, check(*itr));
    return ret;
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&N);
        for(int i=0; i<N; i++){
            int m, b, p;
            bs[i].clear(); ps[i].clear();
            scanf("%d",&m);
            for(int j=0; j<m; j++){
                scanf("%d%d",&b,&p);
                bs[i].push_back(b);
                ps[i].push_back(p);
            }
        }
        printf("%.3f\n",solve());
    }
    return 0;
}