题目 - 通信系统
描述
某通信公司需要购置一个通信系统,这个系统由几个设备组成,每个设备都有几个不同的厂商,他们提供的设备的带宽和价格有所不同。
系统的总带宽B是几个设备中带宽的最小值,而系统的价格P则是几个设备的价格最和。
给出每个设备的所有厂商的设备带宽和价格,请你选择一种方案,使得系统的B/P尽可能大(即同样的价格买到的带宽尽可能大)
关于输入
第一行包含一个整数t(1<=t<=10),表示输入数据的组数,接下来是t组测试数据。
每组测试数据第一行是一个整数n(1<=n<=100),表示通信系统由n个不同的设备组成。
接下来n行,每行是一种设备的厂商信息。第一个整数是mi,表示第i个设备的厂商数目,接下来mi个数对,每个数对表示一个厂商提供的设备的带宽和价格。
关于输出
对每组测试数据,输出最大的B/P值,保留到小数点后3位。
例子输入
1
3
3 100 25 150 35 80 25
2 120 80 155 40
2 100 100 120 110
例子输出
0.649
针对所有的带宽情况,分别计算出最大的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;
}