首页 > 代码库 > LA3971 组装电脑
LA3971 组装电脑
题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1972
题意：
有 b 块钱， n个配件，配件有 种类，名字，价格，和品质。要求每一类都要有，价格总和不能超过 b，最后要求最低的品质的那个配件的品质要最高。
分析：
二分。
二分品质x，低于 x 的筛掉，高于等于 x 的，选一个最便宜的。
处理好每种配件，插到vector中，输入麻烦一点。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int maxn = 1000 + 5; 6 const int inf = 0x3f3f3f3f; 7 int n,b; 8 9 struct Component {10 int price;11 int quality;12 };13 14 vector<Component> comp[maxn];15 16 int cnt;17 map<string,int> id;18 int ID(string s) {19 if(!id.count(s))20 id[s] = cnt++;21 return id[s];22 }23 24 bool ok(int q)25 {26 int sum = 0;27 for(int i=0;i<cnt;i++) {28 int m = comp[i].size();29 int cheap = inf;30 for(int j=0;j<m;j++) {31 if(comp[i][j].quality>=q)32 cheap = min(cheap,comp[i][j].price);33 }34 if(cheap==inf) return false;35 sum+=cheap;36 if(sum>b) return false;37 }38 return true;39 }40 41 int main()42 {43 int t;44 scanf("%d",&t);45 while(t--) {46 cnt = 0;47 int maxq = 0;48 scanf("%d%d",&n,&b);49 for(int i=0;i<n;i++) {50 comp[i].clear();51 }52 53 for(int i=0;i<n;i++) {54 char type[30],name[30];55 int p,q;56 scanf("%s%s%d%d",type,name,&p,&q);57 maxq = max(maxq,q);58 comp[ID(type)].push_back((Component){p,q});59 }60 61 int L = 0,R=maxq+1;62 while(L<R) {63 int M = L + (R-L+1)/2;64 if(ok(M))65 L = M;66 else R = M - 1;67 }68 printf("%d\n",L);69 }70 return 0;71 }
LA3971 组装电脑
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。