题意：
有一个人有b元，要去买零件，有n个零件，零件有不同的种类，名称，价格，质量，要求每种零件买一个，不超过b元钱，让最差质量尽量好，问最差质量是多少。
题解
最小值最大问题，所以二分答案，再去判断是否满足题目要求的每种类型都要选，并不超过所给的金额，可知二分答案的范围是左闭右开 ,ans>=x,否则ans<x。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <vector> #include <cmath> #include <set> #include <map> using namespace std; int t; int cnt; struct node { int m,p; }; map<string,int> mp; //为每一种配件顺序记录编号 int id(string s) { if(!mp.count(s)) mp[s]=cnt++; return mp[s]; } int a,b;//配件数和预算 vector<node> comp[1005]; //判断二分的品质因子是否符合 bool ok(int k) { int sum=0; for(int i=0;i<cnt;i++)//各个种类 { int cheapest=1e9+1;//找到满足不小于k的最小值 int si=comp[i].size(); for(int j=0;j<si;j++) { if(comp[i][j].p>=k) //因为假设的最小因子是k，所以小于k的都不符合 cheapest=min(cheapest,comp[i][j].m); } if(cheapest==1e9+1) return false;//k太大 取不到配件 不满足 sum+=cheapest;//选择第i种配件 if(sum>b) return false; //超出预算 } //printf("sum %d mid %d\n",sum,k); return true; } int main() { scanf("%d",&t); while(t--) { scanf("%d%d",&a,&b); for(int i=0;i<a;i++) comp[i].clear(); mp.clear(); cnt=0;//记录配件的种类 int mx=0;//记录最大的品质因子 while(a--) { char type[30],name[30]; int p,m; scanf("%s%s%d%d",type,name,&m,&p); mx=max(mx,p); comp[id(type)].push_back((node){m,p}); } //二分 int l=0,r=mx,mid; while(l<r) { //printf("l %d r %d\n",l,r); mid=l+(r-l+1)/2;//因为是左闭右开 if(ok(mid)) l=mid; else r=mid-1; } printf("%d\n",l); } return 0; } 最后附上二分的常用边界写法 以避免TLE
