https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1972
http://7xjob4.com1.z0.glb.clouddn.com/df5832a56667ea3317ca9166994f1eb6
题意：给电脑配件，价格和性能，求在指定总价内配件的最低性能最大。
思路：用二分方法，找出性能，使这个性能以上的配件能在指定价格内买到，最小值最大问题。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn=1000+5; 5 6 int n,b,num; 7 char typec[25],namec[25]; 8 int price,quality; 9 int fp[maxn][maxn],fq[maxn][maxn],m[maxn]; 10 11 vector <string> tp; 12 void trans() 13 { 14 int i,j,l; 15 string s=typec; 16 l=tp.size(); 17 for(i=0;i<l;i++) 18 { 19 if(tp[i]==s) 20 { 21 m[i+1]++; 22 fp[i+1][m[i+1]]=price; 23 fq[i+1][m[i+1]]=quality; 24 return; 25 } 26 } 27 tp.push_back(s); 28 m[l+1]++; 29 fp[l+1][m[l+1]]=price; 30 fq[l+1][m[l+1]]=quality; 31 } 32 33 int check(int qu) 34 { 35 int i,j,sum=0; 36 for(i=1;i<=num;i++) 37 { 38 int mi=1000000005; 39 for(j=1;j<=m[i];j++) 40 { 41 if(fq[i][j]>=qu && fp[i][j]<mi) 42 mi=fp[i][j]; 43 } 44 if(mi==1000000005) 45 return 0; 46 sum+=mi; 47 } 48 if(sum<=b) 49 return 1; 50 else 51 return 0; 52 } 53 54 int main() 55 { 56 int T; 57 int i,j; 58 scanf("%d",&T); 59 while(T--) 60 { 61 scanf("%d %d",&n,&b); 62 63 memset(m,0,sizeof(m)); 64 tp.clear(); 65 for(i=1;i<=n;i++) 66 { 67 scanf("%s %s %d %d",typec,namec,&price,&quality); 68 trans(); 69 } 70 num=tp.size(); 71 72 int l=0,r=1000000005; 73 while(l+1<r) 74 { 75 int mid=(l+r)/2; 76 if(check(mid)) 77 { 78 l=mid; 79 } 80 else 81 { 82 r=mid; 83 } 84 } 85 86 printf("%d ",l); 87 } 88 return 0; 89 }