链接：https://vjudge.net/problem/UVA-12124
思路：求最小值最大的题目，一般采取二分的方法，注意本题目输入配件的时候不一定是按照分类顺序输入的，所以需要一个map给每种配件分配一个编号，然后注意二分时新建一个map并赋值为原来map的值，不要直接用原map修改(又错在这种很细节的小地方了)
代码：
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
struct pj{
char a[1000],b[1000];
int cost,q;
}pp[1001];
int t,n,times;//times记录配件的种类个数
long long b;
map<string,int> jj;
map<string,int> kk;//为每个种类配件分配一个编号，因为输入不一定是按照种类分类输入的
int aaa[1001];
bool c(long long d){
int qqq = times;
long long sum = 0;
map<string,int> jjj;//复制一个原来的map
jjj = jj;
for(int i=0;i<times;i++)aaa[i] = 1e9;//全部设为无穷大
for(int i=0;i<n;i++){
if(pp[i].q>=d&&pp[i].cost<aaa[kk[pp[i].a]]){
aaa[kk[pp[i].a]] = pp[i].cost;
}
if(--jjj[pp[i].a]==0)qqq--;
}
for(int i=0;i<times;i++)sum+=aaa[i];
return sum<=b&&qqq==0;
}
int main(){
scanf("%d",&t);
while(t--){
jj.clear();
kk.clear();
times = 0;
scanf("%d%d",&n,&b);
for(int i=0;i<n;++i){
scanf("%s%s%d%d",pp[i].a,pp[i].b,&pp[i].cost,&pp[i].q);
if(jj[pp[i].a]++==0){
kk[pp[i].a] = times++;
}
}
long long lb = 0;
long long ub = 1e9;
while(ub-lb>1){
long long mid = lb+(ub-lb)/2;
if(c(mid))lb = mid;
else ub = mid;
}
printf("%lld\n",lb);
}
return 0;
}
