題目來源：
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種設(shè)備來組一個通信系統(tǒng)，每一種設(shè)備，又是由一些不同的制造商生產(chǎn)的，不同制造商生產(chǎn)的同種設(shè)備會有不同的帶寬和價格。現(xiàn)在你要在每一個設(shè)備的制造商中選一個，使得購買的n種設(shè)備，它們帶寬的最小值與價格之和的比最大。
題目分析：
一開始想到的就是暴搜，但是搜索的深度達到100，時間肯定是不允許的。想要解決這題，必須找到一個好的查找策略。再想想看這題的特點，最后的答案，帶寬是選取所有設(shè)備中的最小值，而價格是選取所有設(shè)備的價格總和。如果某個制造商生產(chǎn)的某種設(shè)備，它的帶寬較高而價格較低，那么選取它的可能性就比較大。再進一步說，如果所選取的n種設(shè)備的帶寬的最小值b已經(jīng)確定，那么對于某種設(shè)備，我們就可以在那些生產(chǎn)這種設(shè)備的，帶寬大于等于b的制造商中進行選擇。當然是選那個價格最低的設(shè)備，因為答案的分子已經(jīng)確定為b，所以分母越小越好。看來只要枚舉b，再對于每個設(shè)備貪心的選擇最小價格就可以了，時間復(fù)雜度為O（mnB），B為帶寬枚舉的數(shù)量。但問題又來了，應(yīng)該怎么枚舉帶寬，題目中并未給出帶寬的取值范圍，如果從0..maxB一個一個枚舉的話，既費時又會造成過多重復(fù)情況（如果枚舉那些在輸入中出現(xiàn)的兩個連續(xù)帶寬之間的值，最后的答案是一樣的）。所以我們應(yīng)該采取某個方法記錄輸入中出現(xiàn)過的帶寬（STL中的set是個不錯的選擇），再枚舉這些帶寬。在枚舉中，可能出現(xiàn)這種情況：枚舉b，選擇了n種設(shè)備，但選擇的所有設(shè)備的帶寬都大于b，那么最終用b/price就不是這種情況的正確答案。其實不用擔(dān)心，因為正確答案一定大于b/price。假設(shè)上面這種情況的實際帶寬最小值是b’，那個當我們再去枚舉b’時，至少有一個設(shè)備的帶寬等于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; //輸入中出現(xiàn)過的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 () //預(yù)處理
{
int i, j, min, b;
//計算所需枚舉的帶寬的最值
maxBand = INT_MAX; //maxBand為所有設(shè)備帶寬最大值的最小值
minBand = INT_MAX; //minBand為所有設(shè)備帶寬最小值的最小值
for (i=0; i<deviceNum; i++)
{
if (
device[i].maxBand < maxBand )
maxBand
= device[i].maxBand;
if (
device[i].minBand < minBand )
minBand
= device[i].minBand;
}
//對于每個設(shè)備，找到帶寬大于等于某一值的最小價格
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;
}