当前位置：凯发ag旗舰厅登录网址下载 > 编程资源 > 编程问答 >内容正文

编程问答

la3971 组装电脑 -凯发ag旗舰厅登录网址下载

发布时间：2025/1/21 编程问答 22 豆豆

凯发ag旗舰厅登录网址下载收集整理的这篇文章主要介绍了 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

总结

以上是凯发ag旗舰厅登录网址下载为你收集整理的la3971 组装电脑的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得凯发ag旗舰厅登录网址下载网站内容还不错，欢迎将凯发ag旗舰厅登录网址下载推荐给好友。

电脑

上一篇：
下一篇： thinikphp 将数据库模型的增、删