poj 1018 Communication System_贪心

题意：给你n个厂，每个厂有m个产品，产品有B（带宽），P（价格），现在要你求最大的 B/P

明显是枚举，当P大于一定值，B/P为零，可以用这个剪枝

#include <iostream>

#include<cstring>

#include<cstdio>

using namespace std;

#define N 110

#define INF 0xffffff

int devb[N][N],devp[N][N];

int b[N*100],tb;

int main(int argc, char** argv) {

	int n,mi[N],i,j,t;

	int blen,minprice,sum,minb,maxb,curb;

	double dmax,tvalue;

	scanf("%d",&t);

	while(t--){

		scanf("%d",&n);

		blen=0;

		for(i=0;i<n;i++){

			scanf("%d",&mi[i]);

			for(j=0;j<mi[i];j++){

				scanf("%d%d",&devb[i][j],&devp[i][j]);

				b[blen++]=devb[i][j];

				if(minb>=devb[i][j])

					minb=devb[i][j];

				if(maxb<=devb[i][j])

					maxb=devb[i][j];

			}

		}

		dmax=0;

		for(tb=minb;tb<=maxb;tb++){

			sum=0;

			curb=INF;

			for(i=0;i<n;i++){

				minprice=INF;

				for(j=0;j<mi[i];j++){

					if(devb[i][j]>=tb&&devp[i][j]<minprice){

						minprice=devp[i][j];

						if(curb>devb[i][j])

							curb=devb[i][j];

					}

				}

				if(minprice==INF)

					break;

				sum+=minprice;

			}

			if(i==n){

				tvalue=(double)curb/sum;

				if(tvalue>dmax)

					dmax=tvalue;

				tb=curb+1;

			}else

				break;

		}

		printf("%.3f\n",dmax);

	}

	return 0;

}