学步园

题意：有b块钱，要装一台电脑，给出n个配件各自的种类、品质因子和贾哥，要求每种类型的配件各买一个，总价不超过b，且“品质最差配件”的品质因子应尽量大，输出最小品质因子的最大值。

思路：解决“最小值最大”的常用方法就是二分答案。假设答案为x，那么删除品质小于x的所有配件，如果能组装出一台电脑，那么正确答案ans>=x，否则ans<x。

如何判定能组装出一台电脑呢？只要在删除品质小于x的所有配件后，取每种配件最便宜的一件，把价格加起来不超过b就可以了。

#include<cstdio>
#include<string>
#include<map>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 1005
#define INF 0x3f3f3f3f
using namespace std;
map< string,int > id;
int T,n,b,cnt;
char tmp[30];
struct Obj {int price,quality,type;}obj[MAXN];
bool cmp(Obj a,Obj b) {return a.quality<b.quality;}
int insert(string s)
{
	if(!id[s]) id[s]=cnt++;
	return id[s];
}
bool check(int x)
{
	int sum=0,kind=0,cheapest[MAXN];
	memset(cheapest,INF,sizeof(cheapest));//记录每件配件的最小价值，初始化都是INF
	
	for(int i=1;i<=n;++i)
	{
		if(obj[i].quality<x) continue;//不考虑品质因子小于x的物品
		if(cheapest[obj[i].type]==INF) ++kind,sum+=obj[i].price,cheapest[obj[i].type]=obj[i].price;
		else if(obj[i].price<cheapest[obj[i].type]) sum=sum-cheapest[obj[i].type]+obj[i].price,cheapest[obj[i].type]=obj[i].price;
	}
	return sum<=b && kind==cnt-1;//如果总价不超过b，而且所选种数等于总种类数（也就是所有种类都选了一件），那么返回true，否则返回false
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&b);
		cnt=1; id.clear();
		int maxquality=0;
		for(int i=1;i<=n;++i)
		{
			scanf("%s",tmp);
			obj[i].type=insert(tmp);
			scanf("%s",tmp);
			scanf("%d %d",&obj[i].price,&obj[i].quality);
			maxquality=max(maxquality,obj[i].quality);
		}
		int low=0,high=maxquality;
		while(low<high)
		{
			int mid=low+(high-low+1)/2;
			if(check(mid)) low=mid;
			else high=mid-1;
		}
		printf("%d\n",low);
	}
	return 0;
}