首页 > 代码库 > LA 3971 组装电脑（二分）
LA 3971 组装电脑（二分）
https://vjudge.net/problem/UVALive-3971
题意：
你有b块钱，想要组装一台电脑。给出n个配件各自的种类、品质因子和价格，要求每种类型的配件各买一个，总价格不超过b，且“品质最差配件”的品质因子应尽量大。
思路：
最小值最大，很明显要二分。
那么怎么判断这个品质因子下钱是够用的呢？
对于每个类型的配件来说，买最便宜的复合品质因子的配件，如果这样都大于b，那就得减小品质因子了。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<stack> 7 #include<queue> 8 #include<cmath> 9 #include<map>10 using namespace std;11 12 const int maxn=1000+5;13 14 int n,b;15 int cnt;16 17 struct node18 {19 int price,quality;20 node(int p,int q):price(p),quality(q){}21 };22 23 map<string,int> id;24 vector<node> comp[maxn];25 26 void init()27 {28 for(int i=0;i<n;i++)29 comp[i].clear();30 id.clear();31 cnt=0;32 }33 34 void ID(string s)35 {36 if(!id.count(s)) id[s]=cnt++;37 }38 39 bool cacl(int m)40 {41 int sum_price=0;42 for(int i=0;i<cnt;i++)43 {44 int min_price=b+1; int k=comp[i].size();45 for(int j=0;j<k;j++)46 {47 if(comp[i][j].quality>=m) min_price=min(min_price,comp[i][j].price);48 }49 if(min_price==b+1) return false;50 sum_price+=min_price;51 if(sum_price>b) return false;52 }53 return true;54 }55 56 int main()57 {58 //freopen("D:\\input.txt","r",stdin);59 int T;60 scanf("%d",&T);61 while(T--)62 {63 scanf("%d%d",&n,&b);64 init();65 66 int maxq=0;67 for(int i=0;i<n;i++)68 {69 char s1[30],s2[30]; int q,p;70 scanf("%s%s%d%d",&s1,&s2,&p,&q);71 ID(s1);72 comp[id[s1]].push_back(node(p,q));73 maxq=max(maxq,q);74 }75 76 int L=0,R=maxq;77 while(L<R)78 {79 int mid=L+(R-L+1)/2; //得这样写，不然会超时80 if(cacl(mid)) L=mid;81 else R=mid-1;82 }83 printf("%d\n",L);84 }85 return 0;86 }
LA 3971 组装电脑（二分）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。