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