組裝電腦（較難題：貪心+模擬（包含C++中STL容器的運用））

2019-11-14 09:50:19

字體：大中小

來源：轉載

供稿：網友

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;}