题意：你有b元钱，想要组装一台电脑，给出n个配件的各自的种类、品质因子和价格，要求每种类型的派件各买一个，总价格不超过b，且“品质最差配件”的品质因子应该尽量大 （题目保证有解），输出配件最小品质因子的最大值
分析：既然题目保证有解，那么每种配件都选品质最差的是一个极端，每种都选品质最好有是一个极端，在两个极端之间二分就可以得到答案。
1 #pragma warning(disable:4786) 2 #include <stdio.h> 3 #include <iostream> 4 #include <string> 5 #include <vector> 6 #include <map> 7 #define zzz 8 using namespace std; 9 int min(int a, int b){ 10 return a<b?a:b; 11 } 12 int max(int a, int b){ 13 return a>b?a:b; 14 } 15 const int MAXN = 1000 + 5; 16 int cnt; 17 map<string, int>id; 18 int ID(string s){ 19 if(!id.count(s)) id[s]=cnt++; 20 return id[s]; 21 } 22 struct ZZ{ 23 int p, q; 24 }; 25 vector<ZZ>zz[MAXN]; 26 int b, n; 27 bool erfen(int q){ 28 int sum = 0; 29 for(int i=0; i<cnt; i++){ 30 int bargin = b + 1; 31 int m = zz[i].size(); 32 for(int j=0; j<m; j++){ 33 if(zz[i][j].q>=q) bargin = min(bargin, zz[i][j].p); 34 } 35 if(bargin == b+1) return false; 36 sum += bargin; 37 if(sum>b) return false; 38 } 39 return true; 40 } 41 int main(){ 42 #ifndef zzz 43 freopen("in.txt", "r", stdin); 44 #endif 45 int cas; 46 scanf("%d", &cas); 47 while(cas--){ 48 scanf("%d%d", &n, &b); 49 cnt = 0; 50 int i; 51 for(i=0; i<n; i++) zz[i].clear(); 52 id.clear(); 53 int maxq = 0; 54 for(i=0; i<n; i++){ 55 char type[30], name[30]; 56 int p, q; 57 scanf("%s%s%d%d", type, name, &p, &q); 58 maxq = max(maxq, q); 59 ZZ tmp; 60 tmp.p = p; 61 tmp.q = q; 62 zz[ID(type)].push_back(tmp); 63 } 64 int l = 0; 65 int r = maxq; 66 while(l<r){ 67 int m = (l+r+1)/2; 68 if(erfen(m)) l = m; 69 else r = m - 1; 70 } 71 printf("%d\n", l); 72 } 73 return 0; 74 }
