/* 思路:本文要求找到满足预算的最好配置的组件,组装计算机,所以可以是按照 *计算机的quantity以标准去查找相应的组件,就可以应用二分法,将每一种组件中的类型都按照质量排序 *选择满足整体质量的要求的情况下的最低价格 */ #include<iostream> #include<string> #include<string.h> #include<algorithm> #include<cstdio> #include<cstring> #define MAX 1010 using namespace std; int budge; int num,m; struct compnent { char type[25]; char name[25]; int quatity; int price; }; struct compnent com[MAX]; int kind[MAX]; bool cmp( compnent a,compnent b) { return (strcmp(a.type,b.type) < 0)||((strcmp(a.type,b.type)==0) && (a.quatity < b.quatity)); } bool judge(int mid) { int b = 0,min; for(int i = 0;i < m-1;i++){ min = 0x3f3f3f3f; for(int j = kind[i];j < kind[i+1];j++){ if(com[j].quatity >= mid){//在每一类中找到质量大于或者等于MID的型号,选择价格较低的 min = (com[j].price < min)?com[j].price:min; } } if(min == 0x3f3f3f3f)//如果为此值那么表示该类别中的质量都小于mid 因为min 是一个超大值 return false; b += min; cout<<min<<endl; } if(b <= budge)//低于预算,则这样的质量可以接受,试着查找更高质量的 return true; else//高出预算,不行找更低质量的 return false; } int main() { int n,max,min; cin>>n; while(n--){ cin>>num>>budge; max = 0; min = 0x3f3f3f3f; for(int i = 0;i < num;i++){ cin>>com[i].type>>com[i].name>>com[i].price>>com[i].quatity;//通过质量大小查找所以先找到最大和最小的值 max = (com[i].quatity > max) ? com[i].quatity : max; min = (com[i].quatity < min) ? com[i].quatity : min; } sort(com,com+num,cmp);//将所有输入同一类的按照质量的大小排序 memset(kind,0,sizeof(kind)); m = 1; for(int i = 1;i < num;i++){//头为0不用再设置 if(strcmp(com[i].type,com[i-1].type))//找到每一类的起始位置也就是前一类的终止位置 kind[m++] = i; } kind[m++] = num;//用于界定第num-1号类型的数量 int high = max,low = min,mid,res = 0; //质量与价格不成正比,行吗? while(low <= high){//通过质量进行二分查找 mid = (low+high)/2; if(judge(mid)){ res = mid; low = mid+1; cout<<"res "<<res<<' '<<mid<<endl; } else{ high = mid-1; } } cout<<res<<endl; } return 0; }
【hoj】2608 assemble 二分法,布布扣,bubuko.com
原文:http://blog.csdn.net/ymzmdx/article/details/35987619