uvalive3971

#pragma warning(disable:4786)
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#define zzz
using namespace std;
int min(int a, int b){
	return a<b?a:b;
}
int max(int a, int b){
	return a>b?a:b;
}
const int MAXN = 1000 + 5;
int cnt;
map<string, int>id;
int ID(string s){
	if(!id.count(s)) id[s]=cnt++;
	return id[s];
}
struct ZZ{
	int p, q;
};
vector<ZZ>zz[MAXN];
int b, n;
bool erfen(int q){
	int sum = 0;
	for(int i=0; i<cnt; i++){
		int bargin = b + 1;
		int m = zz[i].size();
		for(int j=0; j<m; j++){
			if(zz[i][j].q>=q) bargin = min(bargin, zz[i][j].p);
		}
		if(bargin == b+1) return false;
		sum += bargin;
		if(sum>b) return false;
	}
	return true;
}
int main(){
#ifndef zzz
	freopen("in.txt", "r", stdin);
#endif
	int cas;
	scanf("%d", &cas);
	while(cas--){
		scanf("%d%d", &n, &b);
		cnt = 0;
		int i;
		for(i=0; i<n; i++) zz[i].clear();
		id.clear();
		int maxq = 0;
		for(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);
			ZZ tmp;
			tmp.p = p;
			tmp.q = q;
			zz[ID(type)].push_back(tmp);
		}
		int l = 0;
		int r = maxq;
		while(l<r){
			int m = (l+r+1)/2;
			if(erfen(m)) l = m;
			else r = m - 1;
		}
		printf("%d\n", l);
	}
	return 0;
}

题意：你有b元钱，想要组装一台电脑，给出n个配件各自的种类、品质银子和价格，要求每种类型的配件各买一个，总价格不超过b，且“品质最差配件”的品质因子应该尽量大

做法：如果每种配件都买最差的，当然有解，所以二分所有配件的品质就可以

代码：