UVALive 3971 组装电脑

爱被打了一巴掌 2022-07-14 15:55 146阅读 0赞

/\*\*  
你有b元钱，想要组装一台电脑。给出n个配件的种类、品质因子，和价格，  
每种类型的配件各买一个，总价不超过b，求配件最小品质因子的最大值。  
  
sample input  
1  
18 800  
processor 3500\_MHz 66 5  
processor 4200\_MHz 103 7  
processor 5000\_MHz 156 9  
processor 6000\_MHz 219 12  
memory 1\_GB 35 3  
memory 2\_GB 88 6  
memory 4\_GB 170 12  
mainbord all\_onboard 52 10  
harddisk 250\_GB 54 10  
harddisk 500\_FB 99 12  
casing midi 36 10  
monitor 17\_inch 157 5  
monitor 19\_inch 175 7  
monitor 20\_inch 210 9  
monitor 22\_inch 293 12  
mouse cordless\_optical 18 12  
mouse microsoft 30 9  
keyboard office 4 10  
  
sample output  
9  
  
找最大值，二分，假设答案为x  
排除品质因子小于x的所有配件，如果能组装出一台电脑，则ans >= x else ans < x;

\*/

#include <cstdio> #include <map> #include <vector> #include <iostream> #include <string> using namespace std; struct AA { int p, q; AA(int a, int b) { p = a, q = b; } }; map<string, int> id; vector <AA> C[1010]; int cnt = 0; int n, b; int ID(string s) //将map里面的对应关系提取出来 { if(!id.count(s)) id[s] = cnt++; return id[s]; } bool check(int q) { int sum = 0; for(int i = 0; i < cnt; i++) { int mi = b + 1; for(int j = 0; j < C[i].size(); j++) { if(C[i][j].q >= q) mi = min(mi, C[i][j].p); } if(mi == b + 1) return 0; sum += mi; if(sum > b) return 0; } return 1; } int main() { int T; while(scanf("%d", &T) != EOF) { while(T--) { scanf("%d%d", &n, &b); int maxn = 0; cnt = 0; id.clear(); for(int i = 0; i < 1010; i++) C[i].clear(); for(int i = 0; i < n; i++) { string s, name; int p, q; cin >> s >> name >> p >> q; if(q > maxn) maxn = q; C[ID(s)].push_back(AA(p, q)); } int l = 0, r = maxn; while(l < r) { int mid = (l + r + 1) / 2;//取右中位数，因为L可能不更新 if(check(mid)) l = mid;//L可能为结果 else r = mid - 1; } cout << l << endl; } } return 0; }

关于二分的一点总结：

浮点数转换当然是l = mid 或 r = mid，结束条件是 r - l < esp;

整数的时候mid 有两种取法：左中 (l + r) / 2，右中 (l + r + 1) / 2,c++STL中的

例如： l = 2,r = 3; mid 采用上面两种分别可以取到2，3；

如果转换是 l = mid + 1,r = mid-1;那上述两种方式都可以

如果转换是 l = mid; r = mid - 1;

例如我们要求满足不等式 x^3 + 100x <= 1e+6 的最大整数x

如果mid满足那个不等式，那么mid就有可能是答案，所以我们只能将mid送入l，而不是mid + 1；

此时，如果采用左中取mid ，l = 2，r = 3；而3确实答案，mid将一直取到2，且一直送2给 l，l 与 r 不是同一个数，就不会出循环，也就是程序进入了死循环,所以这时只能采用右中方式取mid = (l+r+1)/2;

同理若求满足不等式x^3 + 100x >= 1e+6 的最小整数x,则转换是 l = mid + 1； r = mid 的时候只能采用左中方式取mid= (l+r)/2;

ForwardIter **lower\_bound**(ForwardIter first, ForwardIter last,const \_Tp& val)算法返回一个非递减序列\[first, last)中的第一个大于等于值val的位置。

ForwardIter **upper\_bound**(ForwardIter first, ForwardIter last, const \_Tp& val)算法返回一个非递减序列\[first, last)中第一个大于val的位置.