UVA 12124 Assemble（二分答案）

题目链接：https://vjudge.net/problem/UVA-12124

垃圾vjudge毁我青春！！

首先这道题是解决“最小值最大”的问题，所以要二分答案。

在这里我们二分$quality$，看是否可以组装起一台不超过$b$元的电脑。然后处理时用map映射一下。

AC代码：

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

AC代码