利用二分枚举所有 品质
思路想出来比较好写代码：
#include<cstdio>#include<map>#include<string>#include<vector>#include<set>#include<cstring>#include<algorithm>using namespace std;const int maxn = 1111;//种类 名称 价格 价格因子int n,b;int cnt;int min_v,max_v;struct Th{int price;int level;Th(int x,int y){price = x; level = y;}};map<string,int>List;vector<Th>arr[maxn];void debug(){printf("[%d]\n",cnt);for(int i = 0; i < cnt; i++){printf("-> %d\n",i);for(int j = 0; j < arr[i].size(); j++)printf("%d %d\n",arr[i][j].price,arr[i][j].level);}}void solve(){//printf("%d %d\n",min_v,max_v);int l = min_v, r = max_v;while(l < r){int mid = l + (r – l + 1) / 2;int ok = 1;int price_ans = 0;for(int i = 0; i < cnt; i++){int price = -1;for(int j = 0; j < arr[i].size(); j++){if(arr[i][j].level >= mid){if(price == -1)price = arr[i][j].price;elseprice = min(price,arr[i][j].price);}}if(price < 0){ok = 0; break;}elseprice_ans += price;}if(price_ans > b) ok = 0;if(ok){// [mid ~ r]l = mid;}else// [l ~ mid)r = mid – 1;}printf("%d\n",l);}int main(){int T;scanf("%d",&T);while(T–){scanf("%d%d",&n,&b);List.clear();cnt = 0;min_v = 1100000000;max_v = -1;for(int i = 0; i < n; i++){char kind[50];int price,level;scanf("%s%*s%d%d",kind,&price,&level);min_v = min(min_v,level);max_v = max(max_v,level);string ki(kind);if(!List.count(ki)){List[ki] = cnt ++;}arr[List[ki]].push_back(Th(price,level));}//debug();solve();for(int i = 0; i < cnt; i++) arr[i].clear();}return 0;}
，寂寞时，想想我的影子，我会在远方给你一个微笑;难过时，
