1.题目描述:点击打开链接
2.解题思路:本题要求最小值最大化,一般方法是利用二分查找解决,即每次都枚举一个品质因子x,删除所有品质因子小于x的配件,如果可以组装出一台不超过b元的电脑,那么ans≥b,否则ans<b。那么如何判断是否可以组装出总价不超过b的电脑呢?很简单,只需要选择最便宜的一个即可,如果这样还超出预算,则无解。
本题需要防止TLE,在写二分搜索时候计算中点M时R-L要改为R-L+1,这样使得中点偏向R,以防止陷入死循环。在判断的时候进行适当的优化,比如设置一个cheapest变量表示最便宜的价格,初始为b+1,若枚举完该类型的所有配件后还是b+1,说明无法组装;另外可以在每次累加sum后判断是否已经超过b,如果超过,则无法组装。另外,本题有一个值得学习的地方:整个程序中关键的变量是类型编号,每个配件的价格和品质因子,因此类型名称就不需要保存了。
3.代码:
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<algorithm> #include<string> #include<sstream> #include<set> #include<vector> #include<stack> #include<map> #include<queue> #include<deque> #include<cstdlib> #include<cstdio> #include<cstring> #include<cmath> #include<ctime> #include<functional> using namespace std; int cnt; map<string, int>id; int ID(string s)//给每种类型分配一个ID,由于本题关键的变量只有price和quality,因此无关的属性不需要保存 { if (!id.count(s))id[s] = cnt++; return id[s]; } #define N 1000+5 struct Component { int price; int quality; }; int n, b;//组件的数目,预算 vector<Component>comp[N]; bool ok(int q) { int sum = 0; for (int i = 0; i < cnt; i++) { int cheapest = b + 1, m = comp[i].size(); for (int j = 0; j < m;j++) if (comp[i][j].quality >= q) cheapest = min(cheapest, comp[i][j].price); if (cheapest == b + 1)return false; sum += cheapest; if (sum>b)return false; } return true; } int main() { //freopen("t.txt", "r", stdin); int T; cin >> T; while (T--) { cin >> n >> b; cnt = 0; for (int i = 0; i < n; i++) comp[i].clear(); id.clear(); int maxq = 0; for (int i = 0; i < n; i++) { char type[30], name[30]; int p, q; scanf("%s%s%d%d", type, name, &p, &q); maxq = max(maxq, q); comp[ID(type)].push_back(Component{ p, q }); } int L = 0, R = maxq; while (L < R) { int M = L + (R - L + 1) / 2;//注意,必须要加1,否则可能会无限死循环 if (ok(M))L = M; else R = M - 1; } printf("%d\n", L); } return 0; }