題目來源：
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，所以分母越小越好?？磥碇灰杜eb，再對于每個設備貪心的選擇最小價格就可以了，時間復雜度為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;
}