本文主要是介绍uvalive 3971 - Assemble(二分搜索 + 贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目连接：3971 - Assemble
题目大意：有若干个零件， 每个零件给出的信息有种类， 名称， 价格， 质量， 现在给出一个金额， 要求在这个金额范围内， 将每个种类零件都买一个， 并且尽量让这些零件中质量最小的越大， 输出质量最小的值。
解题思路：首先可以用二分搜索确定质量， 然后在搜索的过程中要判断这个质量是否能被满足， 判断函数可以用贪心， 在每一类的零件中选择价格最低且质量大于等于当前质量的零件。（事先按照价格大小排序）。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 1005;
const int M = 25;struct State {char name[M];int money;int wei;
}s[N][N];
int cnt, sum, son[N];
char str[N][M], sex[M];bool cmp(const State& a, const State& b) {return a.money < b.money;
}int find(char sex[]) {for (int i = 0; i < cnt; i++)if(strcmp(sex, str[i]) == 0)return i;strcpy(str[cnt], sex);return cnt;
}bool judge(int Min) {int tmp = 0;for (int i = 0; i < cnt; i++) {int flag = 1;for (int j = 0; j < son[i]; j++) {if (s[i][j].wei >= Min) {flag = 0;tmp += s[i][j].money;break;}}if (flag || tmp > sum) return false;}return true;
}int main() {State now;int cas, n, cur, L, R;scanf("%d", &cas);while (cas--) {memset(s, 0, sizeof(s));memset(son, 0, sizeof(son));memset(str, 0, sizeof(str));cnt = L = R = 0;scanf("%d%d", &n, &sum);for (int i = 0; i < n; i++) {scanf("%s%s%d%d", sex, now.name, &now.money, &now.wei);if (now.wei > R) R = now.wei;cur = find(sex);s[cur][son[cur]++] = now;if (cur == cnt) cnt++;}for (int i = 0; i < cnt; i++)sort(s[i], s[i] + son[i], cmp);int mid;while (L < R) {mid = (L + R) / 2;if (L == mid) break;if (judge(mid))L = mid;elseR = mid;}if (judge(mid + 1)) mid++;printf("%d\n", mid);}return 0;
}
这篇关于uvalive 3971 - Assemble(二分搜索 + 贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
