针对所有的带宽情况,分别计算出最大的B/P值。
带宽总数为m1+m2+...+mn,暂时不考虑重复情况,然后将每个设备的不同选择情况按价格从小到大排序,于是针对每种带宽选择每个设备满足条件的价格最小的设备,然后求出B/P,因为价格从小到大排序,所以求出的是针对该带宽的最大的B/P,最后求出所有带宽情况下的最大值。
#include <stdlib.h>
#include <iostream>
using namespace std;
struct SYS { int b, p; } sys[100][100];
int cmp(const void * a, const void * b)
{
SYS * c = (SYS *) a;
SYS * d = (SYS *) b;
return c -> p - d -> p;
}
int main()
{
cout.setf(ios_base::showpoint);
cout.setf(ios_base::fixed);
cout.precision(3);
int n;
cin >> n;
while(cin >> n)
{
int m[100], b[10000], bc = 0;
for(int i = 0; i < n; i++)
{
cin >> m[i];
for(int j = 0; j < m[i]; j++)
{
cin >> sys[i][j].b >> sys[i][j].p;
b[bc++] = sys[i][j].b;
}
qsort(sys[i], m[i], sizeof(SYS), cmp);
}
double max = 0;
for(int k = 0; k < bc; k++)
{
int sum = 0;
bool could = true;
for(int i = 0; i < n; i++)
{
int j;
for(j = 0; j < m[i]; j++)
if(sys[i][j].b >= b[k])
{
sum += sys[i][j].p;
break;
}
if(j == m[i])
{
could = false;
break;
}
}
if(could)
{
double temp = double(b[k]) / sum;
max = max > temp ? max : temp;
}
//max >?= double(b[k]) / sum;
}
cout << max << endl;
}
return 0;
}