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

題目描述

輸入

輸出

樣例輸入

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