组装电脑（较难题：贪心+模拟（包含C++中STL容器的运用））

Problem Link：http://139.129.36.234/problem.php?id=1276

1276: 组装电脑

时间限制: 1 Sec   内存限制: 128 MB 提交: 2   解决: 2 [ 提交][ 状态][ 讨论版]

题目描述

你有b块钱，想要组装一台电脑。给出n个配件各自的种类，品质因子和价格，要求每种类型配件给买一个，总价不超过b，且“品质最差的配件”的品质因子尽量大。

输入

输入的第一行为测试数据T(T<=1000)。每组数据的第一行为两个正整数n(1<=n=1000)和b(1<=b<=109)，即配件的数目和预算；以下n行每行描述一个配件，依次为种类，名称，价格和品质因子。其中价格为不超过106的非负整数；品质因子是不超过109的非负整数（越大越好）；种类和名称则由不超过20个字母，数字和下划线组成。输入保证总有解。

输出

对于每组数据，输出配件最小的品质因子的最大值。

样例输入

1 18 800 processor 3500_MHz 66 5 processor 4200_MHz 103 7 processor 5000_MHz 156 9 processor 6000_MHz 219 12 memory 1_GB 35 3 memory 2_GB 88 6 memory 4_GB 170 12 mainbord all_onboard 52 10 harddisk 250_GB 54 10 harddisk 500_FB 99 12 casing midi 36 10 monitor 17_inch 157 5 monitor 19_inch 175 7 monitor 20_inch 210 9 monitor 22_inch 293 12 mouse cordless_optical 18 12 mouse microsoft 30 9 keyboard office 4 10

样例输出

9

提示

来源

北理机试真题

AC code：

#include<iostream> #include<algorithm> #include<stdio.h> #include<map> #include<math.h> #include<string.h> #include<queue> #include<vector> #include<set> #define LL long long #define exp 1e-9 #define MAXN 1000010 using namespace std; struct node{ string kind; string name; int price; int qua; }pro[1010]; map<string,int>m; vector<node> vec[1010]; int cnt; void Classify(string kind,node p) { int i,id; if(m.count(kind)==0) { cnt++; m[kind]=cnt; } id=m[kind]; vec[id].push_back(p); } void buy(int b,int maxq) { int i,j,k,fg,cheapist,sum; for(i=maxq;i>=1;i--) { sum=b; for(j=1;j<=cnt;j++) { fg=0; cheapist=sum+1; for(k=0;k<vec[j].size();k++) { if(vec[j][k].qua>=i && cheapist>vec[j][k].price) { fg=1; cheapist = vec[j][k].price; } } if(!fg) { break; } else { sum-=cheapist; } } if(j==cnt+1) { printf("%d\n",i); break; } } } int main() { // freopen("D:\\in.txt","r",stdin); int T,i,n,b,maxq; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&b); for(i=0;i<=n;i++) vec[i].clear(); m.clear(); cnt=0; maxq=-1; for(i=1;i<=n;i++) { cin>>pro[i].kind>>pro[i].name>>pro[i].price>>pro[i].qua; Classify(pro[i].kind,pro[i]); maxq=max(maxq,pro[i].qua); } buy(b,maxq); } return 0; }