poj 1018

题目大意：

一套通讯系统由一些设备组成，每种设备由不同的供应商供应，每个供应商供应的同种设备有各自的带宽（bandwidth）和价格（prices）。通讯系统的带宽(B)指的是组成该系统的所有设备的带宽的最小值，通讯系统的价格(P)指的是组成该系统的所有设备的价格之和。求最大的 (B / P)。

思路分析：

先枚举出所有供应商所供应的所有设备的最小带宽和最大的带宽，从最小带宽开始枚举，用贪心法选出带宽大于等于最小带宽的最低价格，然后再比较更新最大的(B / P)的值，直到到达最大带宽。

代码如下：

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
const int Max=101;

struct node 
{
	double b;
	double p;
};

node a[Max][Max];
double b[Max*Max];
int m[Max];
int bsize;

int cmp(const void *a,const void *b)
{
	return (*(double *)a)-(*(double *)b);
}

int main()
{
	int t,n;
	cin>>t;
	while (t--)
	{
		memset(a,0,sizeof(a));
		memset(m,0,sizeof(m));
		cin>>n;
		int i,j,k;
		int bsize=0;
		for (i=0;i<n;i++)
		{
			cin>>m[i];
			for (j=0;j<m[i];j++)
			{
				cin>>a[i][j].b>>a[i][j].p;
				b[bsize++]=a[i][j].b;
			}
		}
		qsort(b,bsize,sizeof(b[0]),cmp);
		double mmax=0;
		double mmin;
		double sump=0;
		double temp=0;
		for (i=b[0];i<=b[bsize-1];i++)
		{
			sump=0;
			for (j=0;j<n;j++)
			{
				mmin=32767;
				for (k=0;k<m[j];k++)
				{
					if (a[j][k].b>=i&&a[j][k].p<mmin)
					{
						mmin=a[j][k].p;
					}
				}
				sump+=mmin;
			}
			temp=i*1.0/sump;
			if(temp>mmax)
				mmax=temp;
		}
		printf("%.3lf\n",mmax);

	}
	return 0;
}