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

2019-11-14 09:45:47

字体：大中小

来源：转载

供稿：网友

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个字母，数字和下划线组成。输入保证总有解。

输出

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

样例输入

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