鏈接：https://vjudge.net/problem/UVA-12124
思路：求最小值最大的題目，一般采取二分的方法尾抑，注意本題目輸入配件的時(shí)候不一定是按照分類順序輸入的歇父，所以需要一個(gè)map給每種配件分配一個(gè)編號(hào)蒂培，然后注意二分時(shí)新建一個(gè)map并賦值為原來(lái)map的值，不要直接用原map修改(又錯(cuò)在這種很細(xì)節(jié)的小地方了)
代碼：
#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記錄配件的種類個(gè)數(shù)
long long b;
map<string,int> jj;
map<string,int> kk;//為每個(gè)種類配件分配一個(gè)編號(hào)榜苫，因?yàn)檩斎氩灰欢ㄊ前凑辗N類分類輸入的
int aaa[1001];
bool c(long long d){
int qqq = times;
long long sum = 0;
map<string,int> jjj;//復(fù)制一個(gè)原來(lái)的map
jjj = jj;
for(int i=0;i<times;i++)aaa[i] = 1e9;//全部設(shè)為無(wú)窮大
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;
}
