poj1018：http://poj.org/problem?id=1018
题意：某公司要建立一套通信系统，该通信系统需要n种设备，而每种设备分别可以有m1、m2、m3、...、mn个厂家提供生产，而每个厂家生产的同种设备都会存在两个方面的差别：带宽bandwidths 和 价格prices。现在每种设备都各需要1个，考虑到性价比问题，要求所挑选出来的n件设备，要使得B/P最大。其中B为这n件设备的带宽的最小值，P为这n
件设备的总价。
题解：方法一：暴力枚举。枚举每个bandwidth，然后从剩余的n-1个类中，找出bandwith大于等于这个ban的width而且price最小的那个值，然后求出b/p，每次枚举，然后更新b/p的值。
1 #include<cstring> 2 #include<cstdio> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 int visit[102];//统计每个种类的个数 7 double ban[102][102];//记录每种的b值 8 double price[102][102];//记录每种的p值 9 int cas,n,temp; 10 int main(){ 11 scanf("%d",&cas);//测试组数 12 while(cas--){ 13 scanf("%d",&n); 14 for(int i=1;i<=n;i++){//读取数据 15 scanf("%d",&visit[i]); 16 for(int j=1;j<=visit[i];j++){ 17 scanf("%lf%lf",&ban[i][j],&price[i][j]); 18 } 19 } 20 double ans=0;//记录最终的结果 21 for(int i=1;i<=n;i++){ 22 for(int j=1;j<=visit[i];j++){//枚举每个b值 23 double bb=ban[i][j]; 24 double sum=price[i][j];//初始值应该是该种类这个对应的p，不是0 25 int count=0;//记录剩余的类中有多少是有b值大于该b 26 for(int k=1;k<=n;k++){//暴力剩余的种类 27 if(k==i)continue; 28 double ss=1000000; 29 for(int g=1;g<=visit[k];g++){//选取满足你要求的设备 30 if(ban[k][g]>=bb&&price[k][g]<ss) 31 ss=price[k][g]; 32 } 33 if(ss!=1000000){//如果找到了就更新sum以及count的个数 34 count++; 35 sum+=ss; 36 } 37 } 38 if(count==n-1){//如果满足该条件，说明能从剩余的每个类中找出一个满足要求的 39 if(bb/sum>ans)//更新ans值 40 ans=bb/sum; 41 } 42 } 43 } 44 printf("%.3f ",ans); 45 } 46 }