zoj 1409 Communication System

/*如果要一个物体的多种属性，最好用结构体，不要用二维数组或者多维数组。用多维数组进行关键字排序很不稳定 */ 
/*给每个设备的所有价格排序，每个设备选取恰好比已知带宽大的价格(这个时候的比例最大)  循环每个设备就得到所有价格综合 然后得到该带宽下的B/P
比较所有带宽的B/P 选取最大的就是所求的*/ 
#include <stdlib.h>
#include <stdio.h>
#define true 1
#define false 0 
typedef struct  
{ int b, p; 
}SYS;
SYS 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()
{
     int n,i,j,sum,k,could,t;
     int m[100], bc;
     int b[10000];/*记录每种带宽*/ 
     double max,temp;
     scanf("%d",&t);
    while(t--)
    {
          scanf("%d",&n);
          bc = 0;
          for( i = 0; i < n; i++)
          {
               scanf("%d",&m[i]);
               for( j = 0; j < m[i]; j++)
               {
                    scanf("%d%d",&sys[i][j].b,&sys[i][j].p) ;
                    b[bc++] = sys[i][j].b;/*记录所有带宽的值，然后排序 */
               }
               qsort(sys[i], m[i], sizeof(SYS), cmp);
          }
          max = 0;
          for( k = 0; k < bc; k++)/*循环每个带宽 */
          {
               sum = 0;
               could = true;
               for(i = 0; i < n; i++)/*每个设备 */
               {
                    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)/*如果这个带宽是可行的 */
               {
                    temp = 1.0*b[k]/ sum;
                    max = max > temp ? max : temp;
               }
              }
      printf("%.3lf
",max);
        
    }    
 return 0;
}
/*
1
3
2 120 80 155 40
3 100 25 150 35 80 25
2 100 100 120 110
*/