LA 3971 Assemble（二分）

题目：

给你b元钱，让你组装一台电脑，有n个配件，属性有种类名字价格品质，每种类型选至少一个，并且最小品质最大。输出这个最大的最小品质。

白书上说了，最小值最大的问题一般是二分来求解答案。在这里我们二分这个品质。这个题在判断时因为数据较小，所以线性查找了，如果遇到大数据就要排序+lower_bound了...

代码如下：

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 const int  M=1005;
 5 int cnt,n,b;
 6 map<string,int> id;
 7 int ID(string s)
 8 {
 9     if (!id.count(s))
10     id[s]=cnt++;
11     return id[s];
12 }
13 struct Component
14 {
15     int price,quality;
16 };
17 vector<Component>comp[M];
18 bool ok(int q)
19 {
20     int sum=0;
21     for(int i=0;i<cnt;++i){
22         int cheapest=b+1,m=comp[i].size();
23         for (int j=0;j<m;++j)
24             if (comp[i][j].quality>=q)cheapest=min(cheapest,comp[i][j].price);
25         if (cheapest==b+1) return false;
26         sum+=cheapest;
27         if (sum>b) return false;
28     }
29     return true;
30 }
31 int main()
32 {
33     int t;
34     //freopen("de.txt","r",stdin);
35     scanf("%d",&t);
36     while (t--)
37     {
38         scanf("%d%d",&n,&b);
39         cnt=0;
40         for (int i=0;i<n;++i)
41         comp[i].clear();
42         id.clear();
43         int maxq=0;
44         for (int i=0;i<n;++i)
45         {
46             char type[30],name[30];
47             int q,p;
48             scanf("%s%s%d%d",type,name,&p,&q);
49             maxq=max(maxq,q);
50             comp[ID(type)].push_back((Component){p,q});
51         }
52         int L=0,R=maxq;
53         while(L<R)
54         {
55             int M=L+(R-L+1)/2;
56             if (ok(M))
57             L=M;
58             else
59             R=M-1;
60         }
61         printf("%d
",L);
62     }
63     return 0;
64 }