装机问题，你要装一台电脑，电脑由多个配件组成，给定配件类型 type，名字 name，价格 price，质量等级 quality。在保证预算不超过的前提下求使得电脑质量等级尽可能高的方案。一个电脑的质量等级由质量最低的那个配件等级所决定。
将配件按类型排序，然后二分配件等级，同一个类型的选择价格较低的，由此计算总价格。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 | #include<iostream> #include<algorithm> #include<string> using namespace std; struct fan{ int pr; int qu; char s[50]; }a[1010]; int n,b,k; int f[1010]; bool flag; bool cmp(const fan &c,const fan &d) { if(strcmp(c.s,d.s) == 0) return c.qu > d.qu; return (strcmp(c.s,d.s)<0); } int fun() { int i,k; k=0; f[0]=0; for(i=1;i<=n-1;++i) { if(strcmp(a[i].s,a[i+1].s)!=0) { f[++k]=i; } } f[++k]=n; return k; } bool check(int mid) { int i,j,mins,sum; sum=0; for(i=1;i<=k;++i) { mins=2147483647; for(j=f[i-1]+1;j<=f[i];++j) { if(mid <= a[j].qu) mins = mins < a[j].pr?mins:a[j].pr; else break; } if(mins == 2147483647)return 0; sum += mins; } if(sum > b) return 0; return 1; } int erfen(int MIN,int MAX) { int mid; while(MIN<=MAX) { mid=(MIN+MAX)/2; if(check(mid)) { MIN=mid+1; flag=1; } else MAX=mid-1; } return MAX; } int main() { int ival,i,MAX,MIN,ans; char temp[100]; //name没什么用的，故用一个临时变量 scanf("%d",&ival); while(ival--) { scanf("%d%d",&n,&b); MAX=0; MIN=2147483647; for(i=1;i<=n;++i) { scanf("%s %s %d %d",&a[i].s,temp,&a[i].pr,&a[i].qu); MAX=MAX>a[i].qu?MAX:a[i].qu; MIN=MIN<a[i].qu?MIN:a[i].qu; } sort(a+1,a+n+1,cmp); //cout<<endl<<endl; //for(i=1;i<=n;++i) //{ // cout<<a[i].s; // printf(" %d %d\n", a[i].pr,a[i].qu); //} memset(f,0,sizeof(f)); k=fun();//将不同类type之间交换的位置用数组f[]记录下来,比如 a a b c c c d d 则f[1]=2;f[2]=3;f[3]=6; //for(i=1;i<=k;++i) //cout<<f[i]<<" ";cout<<endl; //cout<<MIN<<" "<<MAX<<endl; flag=0; ans=erfen(MIN,MAX); if(flag==0)printf("0\n"); else printf("%d\n",ans); } return 0; } |
Related posts(相关文章):