尊龙游戏旗舰厅官网
收集整理的这篇文章主要介绍了
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
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 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) {
28 int m = comp[i].size();
29 int cheap = inf;
30 for(int j=0;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) {
50 comp[i].clear();
51 }
52
53 for(int i=0;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 } view code
转载于:https://www.cnblogs.com/treedream/p/6701591.html
总结
以上是尊龙游戏旗舰厅官网为你收集整理的la3971 组装电脑的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得尊龙游戏旗舰厅官网网站内容还不错，欢迎将尊龙游戏旗舰厅官网推荐给好友。
