题意：
你有b块钱想要组装一台电脑。给出n个配件的种类，品质和价格，要求每个种类的配件各买一个总价格不超过b且“品质最差配件”的品质因子应尽量大。
这种情况下STL的map的确很好用，学习学习
这种最大值最小的问题可以用二分法，自己写的二分会死循环，学习一下别人的二分。
1 //#define LOCAL 2 #include <vector> 3 #include <cstdio> 4 #include <string> 5 #include <map> 6 using namespace std; 7 8 int cnt; //组件的类型数 9 map<string, int> id; //将组件类型的名字与编号对应起来 10 int ID(string s) //求类型s的编号 11 { 12 if(!id.count(s)) id[s] = cnt++; 13 return id[s]; 14 } 15 const int maxn = 1000 + 5; 16 struct Component 17 { 18 int price; 19 int quality; 20 }; 21 int n, b; 22 vector<Component> comp[maxn]; 23 24 bool ok(int q) 25 {//品质不小于q的组件能否组成不超过b元的电脑 26 int sum = 0; 27 for(int i = 0; i < cnt; ++i) 28 { 29 int cheapest = b + 1, m = comp[i].size(); 30 for(int j = 0; j < m; ++j) 31 if(comp[i][j].quality >= q) 32 cheapest = min(cheapest, comp[i][j].price); 33 //选择品质因子不小于p的最便宜的配件 34 if(cheapest > b) return false; 35 sum += cheapest; 36 if(sum > b) return false; 37 } 38 return true; 39 } 40 41 int main(void) 42 { 43 #ifdef LOCAL 44 freopen("3971in.txt", "r", stdin); 45 #endif 46 47 int T; 48 scanf("%d", &T); 49 while(T--) 50 { 51 scanf("%d%d", &n, &b); 52 cnt = 0; 53 for(int i = 0; i < n; ++i) comp[i].clear(); 54 id.clear(); 55 56 int maxq = 0; 57 for(int i = 0; i < n; ++i) 58 { 59 char type[30], name[30]; 60 int p, q; 61 scanf("%s%s%d%d", type, name, &p, &q); 62 maxq = max(maxq, q); 63 comp[ID(type)].push_back((Component) {p, q}); 64 } 65 66 int L = 0, R = maxq; 67 while(L < R) 68 { 69 int M = L + (R - L + 1) / 2; 70 if(ok(M)) 71 L = M; 72 else 73 R = M - 1; 74 } 75 printf("%d ", L); 76 } 77 return 0; 78 }