Assemble hoj 不错的二分题 稍有繁琐
/*大致的题意就是从每一种类型的组件里挑选一样，使得所有部件里面最便宜的那个价钱尽量高，而所有部件的钱数综合又不超过给定值。这道题感觉比较难写。首先定义结构体，然后对里面的所有元素进行排序。然后对同一个type里的部件在满则quality的要求去价钱的最小值。*/#include <iostream>#include <stdio.h>#include <cstring>#include <string>#include <algorithm>using namespace std;int t,n,m;const int mm=10000001;struct LEI{ string type; string name; int p; long long q;} lei[1005];bool cmp(LEI a,LEI b){ if(a.type!=b.type) return a.type<b.type; else if(a.q!=b.q) return a.q<b.q; else if(a.name!=b.name) return a.name<b.name; else return a.p<b.p;}bool check(long long mid){ int start=0,sum=0; for(int i=0; i<n; i++) { if(lei[i].type==lei[i+1].type&&i+1<n) continue; else { int min=mm; for(int j=start; j<=i; j++) { if(lei[j].q>=mid) { if(lei[j].p<min) min=lei[j].p; } } if(min==mm) return false;//等号成立,说明没有一个满足lei[j].q>=mid.即错误. else sum+=min; start=i+1; } } if(sum<=m) return true; else return false;}int main(){ scanf("%d",&t); while(t--) { long long min=1000000001,max=0; scanf("%d%d",&n,&m); for(int i=0; i<n; i++) { cin >> lei[i].type; cin >> lei[i].name; scanf("%d",&lei[i].p); scanf("%lld",&lei[i].q); if(lei[i].q>max) max=lei[i].q; if(lei[i].q<min) min=lei[i].q; } sort(lei,lei+n,cmp); long long mid=0,ans=0; while(min<=max) { mid=(min+max)/2; if(check(mid)) { ans=mid; min=mid+1; } else max=mid-1; } printf("%lld\n",ans); } return 0;}