UVALive 3971-Assemble - 최소값 최대화(2점)

제목: 당신은 b위안의 돈이 있습니다. 컴퓨터 한 대를 조립하고 싶습니다. n개의 부품 각자의 종류, 품질 은과 가격을 제시하고 각 종류의 부품을 각각 하나씩 사도록 요구합니다. 총 가격은 b를 초과하지 않으며'품질 최악의 부품'의 품질 인자는 가능한 한 커야 합니다.
이분 품질 인자
매번 종류별 부품 중 품질 개선 인자 X보다 큰 가장 싼 부품을 선택하고, 합쳐서 b를 초과하지 않으면 가능하다. 그렇지 않으면 더욱 작은 품질 인자를 선택해야 한다.
코드:
ac 코드:

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <vector>
using namespace std;
const int inf =2147483640;
struct node
{ 
	int q;
	int p;
	bool operator<(const node &b)const
	{
		return q<b.q;
	}
};
int min(int a,int b)
{return a<b?a:b;}
map <string,int> uu;
vector<node> tm[1005];
vector<node>::iterator it;
node point[1005];
int cun=0;

int n,b;
int main()
{ 
	int  ok(int x);
	int  t;
	cin>>t;
	while(t--)
	{
		int i;
		for (i=1;i<=n;i++)
			tm[i].clear();
		
		uu.clear();
		
		scanf("%d%d",&n,&b);
		char tmp[35];
		char type[35];
		int minn=inf;
		int maxx=0-1;
		cun=0;
		for (i=1;i<=n;i++)
		{
			scanf("%s %s %d %d",type,tmp,&point[i].p,&point[i].q);
			string ss=type;
			if (uu.find(ss)==uu.end())
				uu[type]=++cun;
			
			int id=uu[type];
			tm[id].push_back(point[i]);
			if (point[i].q<minn)
				minn=point[i].q; 
			if (point[i].q>maxx)
				maxx=point[i].q; 
			
		}
		
		for (i=1;i<=cun;i++)
			sort(tm[i].begin(),tm[i].end());
		
		int l=minn;
		int r=maxx;
		
		while(l<=r)  
        {  
            int mid=(l+r)/2;  
            if (r-l==0) //          
                break;  
            if (r-l==1)//2 1  
            {  
                if (!ok(r))    r=l; 
				break;  
            }  
            if (ok(mid))//    ， 
                l=mid;      //mid      
            else  
                r=mid-1;       //mid       
        }  
		
        printf("%d
",r);
		
	}
	
	return 0;
	
}

int  ok(int x)
{
	int sum=0;
	int i;
	node tmp; tmp.q=x; 
	for (i=1;i<=cun;i++)
	{
		
	 	it=lower_bound(tm[i].begin(),tm[i].end(),tmp);
		if (it==tm[i].end()) return 0; //****         X   ***            
		int cheapest=it->p;         
		for (it;it!=tm[i].end();it++)
		{
			cheapest=min(cheapest,it->p);
		}  
		sum+=cheapest;
	}
	if (sum>b)
		return 0;
	else 
		return 1; 
}