题目来源：
PKU 1018 Communication System
算法分类：
枚举+贪心
原文：
Communication System
Time
Limit:1000MS Memory Limit:10000K
Description
We have received an order from
Pizoor Communications Inc. for a special communication system. The system
consists of several devices. For each device, we are free to choose from
several manufacturers. Same devices from two manufacturers differ in their
maximum bandwidths and prices.
By overall bandwidth (B) we mean the minimum of the bandwidths of the chosen
devices in the communication system and the total price (P) is the sum of the
prices of all chosen devices. Our goal is to choose a manufacturer for each
device to maximize B/P.
Input
The first line of the input file
contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by
the input data for each test case. Each test case starts with a line containing
a single integer n (1 ≤ n ≤ 100), the number of devices in the communication
system, followed by n lines in the following format: the i-th line (1 ≤ i ≤ n)
starts with mi (1 ≤ mi ≤ 100), the number of manufacturers for the i-th device,
followed by mi pairs of positive integers in the same line, each indicating the
bandwidth and the price of the device respectively, corresponding to a
manufacturer.
Output
Your program should produce a single
line for each test case containing a single number which is the maximum
possible B/P for the test case. Round the numbers in the output to 3 digits
after decimal point.
Sample Input
1
3
3
100 25 150 35 80 25
2
120 80 155 40
2
100 100 120 110
Sample Output
0.649
Source
Tehran 2002, First Iran Nationwide
Internet Programming Contest
中文描述：
你需要购买n种设备来组一个通信系统，每一种设备，又是由一些不同的制造商生产的，不同制造商生产的同种设备会有不同的带宽和价格。现在你要在每一个设备的制造商中选一个，使得购买的n种设备，它们带宽的最小值与价格之和的比最大。
题目分析：
一开始想到的就是暴搜，但是搜索的深度达到100，时间肯定是不允许的。想要解决这题，必须找到一个好的查找策略。再想想看这题的特点，最后的答案，带宽是选取所有设备中的最小值，而价格是选取所有设备的价格总和。如果某个制造商生产的某种设备，它的带宽较高而价格较低，那么选取它的可能性就比较大。再进一步说，如果所选取的n种设备的带宽的最小值b已经确定，那么对于某种设备，我们就可以在那些生产这种设备的，带宽大于等于b的制造商中进行选择。当然是选那个价格最低的设备，因为答案的分子已经确定为b，所以分母越小越好。看来只要枚举b，再对于每个设备贪心的选择最小价格就可以了，时间复杂度为O（mnB），B为带宽枚举的数量。但问题又来了，应该怎么枚举带宽，题目中并未给出带宽的取值范围，如果从0..maxB一个一个枚举的话，既费时又会造成过多重复情况（如果枚举那些在输入中出现的两个连续带宽之间的值，最后的答案是一样的）。所以我们应该采取某个方法记录输入中出现过的带宽（STL中的set是个不错的选择），再枚举这些带宽。在枚举中，可能出现这种情况：枚举b，选择了n种设备，但选择的所有设备的带宽都大于b，那么最终用b/price就不是这种情况的正确答案。其实不用担心，因为正确答案一定大于b/price。假设上面这种情况的实际带宽最小值是b’，那个当我们再去枚举b’时，至少有一个设备的带宽等于b’，这次得到的答案也就是上面那种情况的答案，所以最终还是能得到正确解。
代码：
#include
<iostream>
#include
<map>
#include
<set>
#include
<climits>
using
namespace std;
const int
MAX = 105;
struct Info
{
int band, price;
};
struct
Device
{
int manuNum;
Info info[MAX];
map<int, int> minPrice; //map[i] = j 表示带宽>=i的最小价格是j
int minBand, maxBand;
};
Device
device[MAX];
int
deviceNum;
set<int>
band; //输入中出现过的band
set<int>::iterator
start, end;
int
maxBand, minBand; //需要枚举的band的最值
int cmp(
const void *a , const void *b )
{
Info *c = (Info *)a;
Info *d = (Info *)b;
if(c->band != d->band)
return
d->band - c->band;
else
return
c->price - d->price;
}
void Input
()
{
int i, j, max, min;
band.clear();
cin>>deviceNum;
for (i=0; i<deviceNum; i++)
{
device[i].minBand
= INT_MAX;
device[i].maxBand
= -1;
cin>>device[i].manuNum;
for (j=0;
j<device[i].manuNum; j++)
{
cin>>device[i].info[j].band>>device[i].info[j].price;
band.insert(device[i].info[j].band);
if
( device[i].info[j].band > device[i].maxBand )
device[i].maxBand
= device[i].info[j].band;
if
( device[i].info[j].band < device[i].minBand )
device[i].minBand
= device[i].info[j].band;
}
}
}
void Pre () //预处理
{
int i, j, min, b;
//计算所需枚举的带宽的最值
maxBand = INT_MAX; //maxBand为所有设备带宽最大值的最小值
minBand = INT_MAX; //minBand为所有设备带宽最小值的最小值
for (i=0; i<deviceNum; i++)
{
if (
device[i].maxBand < maxBand )
maxBand
= device[i].maxBand;
if (
device[i].minBand < minBand )
minBand
= device[i].minBand;
}
//对于每个设备，找到带宽大于等于某一值的最小价格
for (i=0; i<deviceNum; i++)
{
//band从大到小，band相等时price从小到大
qsort(device[i].info,
device[i].manuNum, sizeof(Info), cmp);
device[i].minPrice.clear();
min =
device[i].info[0].price;
b =
device[i].info[0].band;
device[i].minPrice[b]
= min;
for (j=1;
j<device[i].manuNum; j++)
{
if
( device[i].info[j].band == b )
continue;
if
( device[i].info[j].price < min )
{
min
= device[i].info[j].price;
}
b
= device[i].info[j].band;
device[i].minPrice[b]
= min;
}
}
}
void Solve
()
{
Pre();
int b, i, totalPrice;
double rate, ans;
map<int, int>::iterator
it;
ans = 0;
start = band.find(minBand);
end = band.find(maxBand);
end ++;
while ( start != end )
{
b = *start;
start ++;
totalPrice = 0;
for (i=0;
i<deviceNum; i++)
{
//找到带宽大于等于b的最小价格
for
(it=device[i].minPrice.begin(); it!=device[i].minPrice.end(); it++)
{
if
( it->first >= b )
{
totalPrice
+= it->second;
break;
}
}
}
rate = double(b)
/ totalPrice;
if ( rate >
ans )
ans
= rate;
}
printf("%.3f\n", ans);
}
int main ()
{
int test;
cin>>test;
while ( test -- )
{
Input ();
Solve ();
}
return 0;
}