本文主要是介绍UVA - 12124 Assemble，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：你有b块钱，给出n个配件各自的种类，品质因子和价格，要求每种类型的都要买一个，总价格不超过b,且品质最差配件的品质因子要尽量大
思路：二分，设答案是x,删除品质因子小于x的所有配件，如果可以组装出不超过b的电脑，那么答案>=x,否则答案<x,每次选出每一类符合的配件中最便宜的一个。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
const int MAXN = 1005;int cnt;
map<string,int> id;
struct Component{int price;int quality;
};
int n,b;
vector<Component> comp[MAXN];int ID(string s){if (!id.count(s))id[s] = cnt++;return id[s];
}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(){int t;scanf("%d",&t);while (t--){scanf("%d%d",&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;if (ok(M))L = M;else R = M -1;}printf("%d\n",L);}return 0;
}这篇关于UVA - 12124 Assemble的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
