題目鏈接：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 } View Code

?

轉載于:https://www.cnblogs.com/TreeDream/p/6701591.html

總結

以上是生活随笔為你收集整理的LA3971 组装电脑的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。