有n个物品 属性有 种类 名字（没用）价格 品质 每种类型选一个 使总价格不超过b 并且最小品质最大 二分品质
#include #include #include #include #include #include #include using namespace std; const int MAXN = 1010; int cnt; int n,m; map id; struct node { int pri; int qua; }; int ID(string s) { if(!id.count(s)) id[s] = cnt++; return id[s]; } vector a[MAXN]; bool ok(int q) { int sum = 0,i,j; for(i = 0; i < cnt; i++) { int len = a[i].size(); int cheap = m + 1; for(j = 0; j < len; j++) { if(a[i][j].qua > = q) cheap = min(cheap,a[i][j].pri); } if(cheap > m) return false; sum += cheap; if(sum > m) return false; } return true; } int main() { char s1[30]; char s2[30]; int t; int i,j; int l,r,maxq; scanf("%d",&t); while(t--) { scanf("%d %d",&n,&m); cnt = 0; maxq = 0; for(i = 0; i < n; i++) a[i].clear(); id.clear(); int p,q; for(i = 1;i <= n; i++) { scanf("%s %s %d %d",s1,s2,&p,&q); maxq = max(maxq,q); a[ID(s1)].push_back((node){p,q}); } l = 0; r = maxq; while(l < r) { int M = l + (r-l+1)/2; //(l+r)>>1 这样会超时的 if(ok(M)) l = M; else r = M - 1; } printf("%d\n",l); } return 0; }