题意：
给出n个工厂的产品参数带宽b和价格p，在这n个工厂里分别选1件产品共n件，使B/P最小，其中B表示n件产品中最小的b值，P表示n件产品p值的和。
输入 iCase n
表示iCase个样例n个工厂
m1 p1 b1 p2 b2..pm1 bm1 //第一个工厂有m1个同种类不同参数的产品，每一个产品的参数分别是p1 b1 p2 b2
m2 p1 b1 p2 b2..pm2 bm2
...
mn p1 b1 p2 b2..pmn bmn
思路：
排序，先把b从小到大排序，然后把p从小到大排序，最后让第几个工厂的序号从小到大排序
排完后就可以直接枚举了，枚举bi，固定了bi之后就枚举pj，取每一个工厂里满足bj比bi大的就加起来，然后计算哪一个值最大..
Tip：
其中有一些优化就是剪枝：
①. 因为最后肯定要有n个bj比bi大，所以bi枚举到sum-(n-1)就可以了，sum表示总共有多少个产品..
②. 如果枚举到bi比某一个公司的所有产品的b都大的时候，就不用往后枚举了，因为产品是按b排过序的，题目要求n-1个公司里面选取的b都要比当前bi大，既然当前bi比某一个公司的所有b都大了，则该公司无法选取符合条件的产品，而后面产品b都比bi大，就跟不可能选取到符合条件的产品了，所以就可以直接break;
③. 如果枚举到某一个bi的时候，bj比bi大的公司个数不满n个的话bi后面的b也可以不枚举了，原因同上..
Code：
1 #include <stdio.h> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int MAXN = 110; 7 8 struct Div 9 { 10 int id; 11 int p; 12 int b; 13 }_div[MAXN*MAXN]; 14 int maxB[MAXN]; 15 16 int cmp(Div a, Div b) 17 { 18 if (a.b != b.b) return a.b < b.b; 19 else if (a.p != b.p) return a.p < b.p; 20 else return a.id < b.id; 21 } 22 23 24 int main() 25 { 26 // freopen("in.txt", "r", stdin); 27 int iCase, n, m, sum; 28 //int vis; 29 bool vis[MAXN]; 30 double ans; 31 bool flag; 32 scanf("%d", &iCase); 33 while (iCase--) { 34 sum = ans = 0; 35 memset(maxB, 0, sizeof(maxB)); 36 flag = true; 37 38 scanf("%d", &n); 39 for (int i = 0; i < n; ++i) { 40 scanf("%d", &m); 41 while (m--) { 42 scanf("%d %d", &_div[sum].b, &_div[sum].p); 43 maxB[i] = max(maxB[i], _div[sum].b); 44 _div[sum++].id = i; 45 } 46 } 47 48 sort(_div, _div+sum, cmp); 49 50 for (int i = 0; i < sum-(n-1); ++i) { 51 int P = _div[i].p; 52 int count = 1; 53 // vis = (1<<n)-1; 54 // vis ^= (1<<_div[i].id); 55 memset(vis, false, sizeof(vis)); 56 vis[_div[i].id] = true; 57 for (int j = i+1; j < sum; ++j) 58 // if (vis & (1<<_div[j].id)) { 59 if (!vis[_div[j].id]) { 60 if (maxB[_div[j].id] < _div[i].b) { 61 flag = false; 62 break; 63 } 64 P += _div[j].p; 65 //vis ^= (1<<_div[j].id); 66 vis[_div[j].id] = true; 67 count++; 68 } 69 if (count < n || !flag) break; 70 ans = max(ans, (double)_div[i].b/P); 71 } 72 printf("%.3lf ", ans); 73 } 74 return 0; 75 }