題意：
若干電腦配件，若干型號，每個(gè)型號都有價(jià)格和性能指數(shù)。求在K錢內(nèi)的配置方案，使得最差性能最好。。
解法：
二分+判斷
代碼：
1
# include <cstdio>
2# include <string>
3# include <cstring>
4# include <map>
5# include <set>
6# include <algorithm>
7# include <vector>
8using namespace std;
9struct node
10
{
11
string name;
12 int p,q;
13
node(string na,int pr,int qu):name(na),p(pr),q(qu) {};
14
};
15struct cmp
16{
17 bool operator()(const node &a,const node &b) const
18 {
19 return a.name<b.name;
20
}
21};
22int n,m;
23map<string,vector<node> >data;
24vector<int> refer;
25bool chk(int mid)
26{
27 long long total=0;
28 for(map<string,vector<node> >::iterator i=data.begin();i!=data.end();i++)
29 {
30 int tp=0xfffffff;
31 for(vector<node>::iterator j=(i->second).begin();j!=(i->second).end();j++)
32 if(j->q>=mid&&j->p<tp)
33 tp=j->p;
34 total+=tp;
35 }
36 return total<=(long long)m;
37}
38int main()
39{
40 int test;
41 scanf("%d",&test);
42 while(test--)
43 {
44 scanf("%d%d",&n,&m);
45 data.clear();
46 refer.clear();
47 for(int i=0;i<n;i++)
48 {
49 char type[128],name[128];
50 int p,q;
51 scanf("%s%s%d%d",type,name,&p,&q);
52 data[string(type)].push_back(node(string(name),p,q));
53 refer.push_back(q);
54 }
55 sort(refer.begin(),refer.end());
56 vector<int>::iterator end=unique(refer.begin(),refer.end());
57 while(refer.end()!=end) refer.pop_back();
58 int s=0,e=refer.size()-1;
59 while(s<=e)
60 {
61 int mid=(s+e)>>1;
62 if(chk(refer[mid])) s=mid+1;
63 else e=mid-1;
64 }
65 printf("%d\n",refer[s-1]);
66 }
67 return 0;
68}
69
70