前言
此题坑爹啊，描述上有误啊，不玩war3做不出来啊！
比赛时同学说这是道纯模拟，纯模拟我擅长啊，但是这一写就是300行啊，还没写完啊！就算写完也肯定不对啊，因为是按描述理解的啊！
但是这么坑爹的题，也有队伍过啊！一过还他么几十个队啊！OMG啊！坑爹啊！
题目大意
模拟魔兽争霸的装备购买行为。在游戏中，可以购买三种装备：
- 普通装备：每个普通装备占一个装备栏，可以直接购买。
- 合成装备：每个合成装备占一个装备栏，购买时需要有足够的材料和合成金。
- 消耗装备：多个同类型的合成装备占一个装备栏。
另外，还有一些规则上需要注意的地方：
- 当你的背包满时，你不能购买任何东西。
- 当你购买合成装备时，相应材料将会从装备栏中消失。
- 当一个操作非法时，现有装备和金钱不会出现任何变化。
- 刚开始时，你的金钱为0，没有任何装备。
- 金钱不能为负数。
思路
纯模拟题。题意稍微有些歧义，不玩war3的同学很难作对这道题。下面说些需要注意的地方：
首先，装备栏满时不可以购买普通装备，这个很正常。对于消耗型装备，装备栏满时，就算已拥有同类型装备，也不能继续购买。但是，合成装备却与以上两种装备不同，在装备栏满时，只要合成金和材料充足，就可以购买！这里就与题目描述相违了。但合成装备有一种特殊情况，就是会出现不需要任何材料的合成装备，这时在规则上可以将其视为普通装备。
因为本人基本没什么war3经验，特地请教了在这个领域里比较拔尖的同学，问其合成装备的材料能否是消耗型装备，得到回答是否，但这个回答让我wa了很久。杭电的测试数据中有用消耗型装备充当材料的情况，并且考虑到了“装备栏满时，消耗型装备数量大于合成需求量导致无法空出装备栏，结果没地方给合成装备”这样的情形。
关于物品价值方面，由于合成装备的材料可以是其他合成装备，因此求取物品价值是一个递归的过程。
代码
#include<iostream>
#include<stdio.h>
#include<map>
#include<string>
using namespace std;
#define NAMESIZE 15
#define EQUIPSIZE 20
int total_room;
//目前拥有的空间
int total_gold;
//目前拥有的金币数量
char list_equipment[6][NAMESIZE+1];
//目前拥有的装备的列表
int total_normal;
//普通装备数量
struct p1
{
string name;
//装备名称
int value;
//装备价值
}normal[EQUIPSIZE];
int total_mixture;
//混合装备数量
struct p2
{
string name;
//装备名称
int value;
//合成价格
int num;
//合成需要的装备种类的数量
string need_name[6];
//合成需要的装备的种类
int need_num[6];
//对应合成所需的各种装备的数量
}mixture[EQUIPSIZE];
int total_consume;
//消耗型装备数量
struct p3
{
string name;
//装备名称
int value;
//装备价值
int num;
//拥有该装备的数量，此参数在init()中被初始化。
}consume[EQUIPSIZE];
void init()
//初始化
{
total_room=0;
total_gold=0;
}
int check_num(const char temp[])
//检查字符串name[]是否表示一个整数。若是整数，返回其大小，否则返回-1。
{
int len=strlen(temp),sum=0;
for(int i=len-1,j=1;i>=0;i--,j*=10)
if(temp[i]>='0'&&temp[i]<='9')
sum+=(temp[i]-'0')*j;
else
return -1;
return sum;
}
pair<int,int> check_exist(const char name[])
//检查装备列表中是否存在装备name,返回值为pair<装备数量，装备列表中的位置。>
//若是消耗型装备，total==1时表示装备栏中有此装备，但并不表示其数量为1。
//消耗型装备的数量记录在对应类型的结构体中。
{
int total=0,pos;
//total表示该装备在装备列表中的数量。
//pos表示该装备在装备列表中的位置。
for(int i=0;i<total_room;i++)
if(!strcmp(list_equipment[i],name))
{
pos=i;
total++;
}
return pair<int,int>(total,pos);
}
pair<int,int> get_type(const char name[])
//获取装备name的类别信息，返回值为pair<类别，在类别中的位置>
//类别：分别用1、2、3表示普通、混合、消耗型装备。
{
for(int i=0;i<total_normal;i++)
if(!strcmp(normal[i].name.c_str(),name))
return pair<int,int>(1,i);
for(int i=0;i<total_mixture;i++)
if(!strcmp(mixture[i].name.c_str(),name))
return pair<int,int>(2,i);
for(int i=0;i<total_consume;i++)
if(!strcmp(consume[i].name.c_str(),name))
return pair<int,int>(3,i);
return pair<int,int>(-1,-1);
//若找不到，返回pair<-1,-1>。
}
int get_value(const char name[])
//获取装备name的价值。
{
pair<int,int> equip_type_info=get_type(name);
//equip_type_info装备name的类别信息。
if(equip_type_info.first==1)
return normal[equip_type_info.second].value;
else if(equip_type_info.first==2)
//如果是混合装备，需要计算材料成本。
{
p2* equip_info=&mixture[equip_type_info.second];
//equip_info指向该混合装备的结构体
int sum=equip_info->value;
//sum表示混合装备的价值
for(int i=0;i<equip_info->num;i++)
//遍历所有材料的种类
sum+=get_value(equip_info->need_name[i].c_str())*(equip_info->need_num[i]);
return sum;
}
else
{
p3* equip_info=&consume[equip_type_info.second];
return equip_info->value*equip_info->num;
}
}
void delete_equip(const char name[],bool sell=true,int num=-1)
//删除装备列表中的name装备
//参数sell用于判断当前操作是删去装备（合成时删去材料）还是卖掉装备。
//num==-1时，表示要删除一个装备栏中的内容。支持所有类型装备。
//num>=0时，表示要删除num个消耗型装备。只支持消耗型装备。
//当num>=0时，sell属性无意义，只支持删除装备，不支持卖装备。
{
if(num==-1)
{
pair<int,int> equip_list_info=check_exist(name);
if(equip_list_info.first)
//若拥有该装备（数量不为0）
{
for(int i=equip_list_info.second+1;i<total_room;i++)
//利用循环将装备从装备列表中删除。
strcpy(list_equipment[i-1],list_equipment[i]);
total_room--;
if(sell)
//如果是卖出装备，则需要更新total_gold。
total_gold+=get_value(name);
pair<int,int>equip_type_info=get_type(name);
if(equip_type_info.first==3)
//若该装别是消耗型装备，则将其装备数量标记为0。
consume[equip_type_info.second].num=0;
}
}
else
{
pair<int,int>equip_type_info=get_type(name);
consume[equip_type_info.second].num-=num;
if(consume[equip_type_info.second].num==0)
//当消耗型装备的数量为0时，需要将其从装备列表中删除，采用递归调用方式。
delete_equip(consume[equip_type_info.second].name.c_str(),false);
}
}
void add_equip(const char name[])
//向装备列表中添加装备name
{
int add_gold=check_num(name);
if(add_gold!=-1)
//若name表示金钱
{
total_gold+=add_gold;
return;
}
pair<int,int> equip_type_info=get_type(name);
//获取装备name的信息。
if(equip_type_info.first==1)
//若是普通装备
{
if(total_room==6)
//若装备栏已满
return;
int equip_value=normal[equip_type_info.second].value;
if(total_gold>=equip_value)
{
total_gold-=equip_value;
strcpy(list_equipment[total_room++],name);
}
}
else if(equip_type_info.first==2)
//若是混合装备
{
p2* equip_info=&mixture[equip_type_info.second];
if(total_gold>=equip_info->value)
//若当前金币总数不满足合成价格。
{
int sum=0;
//sum表示，因增加mixture装备所新增空余装备栏的数量。
for(int i=0;i<equip_info->num;i++)
//利用循环判断是否有足够的材料。
{
const char* temp_name=equip_info->need_name[i].c_str();
//temp_name表示mixture装备所需的材料名称。
if(get_type(temp_name).first!=3)
//若材料不是消耗型
if(check_exist(temp_name).first<equip_info->need_num[i])
return;
else
sum+=equip_info->need_num[i];
else
//若材料是消耗型。
{
int temp_num=consume[get_type(temp_name).second].num;
//temp_num表示消耗型材料的数量。
if(temp_num<equip_info->need_num[i])
return;
else if(temp_num==equip_info->need_num[i])
//若消耗型材料的数量与所需数量相等，则可以空出一个装备栏。
sum++;
}
}
if(total_room-sum+1>6)
//若装备栏的容量符合要求
return;
total_gold-=equip_info->value;
//更新total_gold
for(int i=0;i<equip_info->num;i++)
//利用循环删除材料。
{
const char* temp_name=equip_info->need_name[i].c_str();
if(get_type(temp_name).first!=3)
for(int j=0;j<equip_info->need_num[i];j++)
delete_equip(temp_name,false);
else
delete_equip(temp_name,false,equip_info->need_num[i]);
}
strcpy(list_equipment[total_room++],name);
}
}
else if(equip_type_info.first==3)
{
if(total_room==6)
//若装备栏已满
return;
p3* equip_info=&consume[equip_type_info.second];
if(total_gold>=equip_info->value)
{
total_gold-=equip_info->value;
equip_info->num++;
if(!check_exist(name).first)
//若装备列表中没有同类的消耗装备
strcpy(list_equipment[total_room++],name);
}
}
else if(equip_type_info.first==-1)
//无该装备
return;
}
void input_normal_info()
//输入普通装备信息
{
char equip_name[NAMESIZE];
//装备的名称
int equip_value;
//装备的价值
for(int i=0;i<total_normal;i++)
{
scanf("%s %d",equip_name,&equip_value);
normal[i].name=equip_name;
normal[i].value=equip_value;
}
}
void input_mixture_info()
//输入合成装备信息
{
char equip_name[NAMESIZE];
//装备的名称
int consume_value;
//consume_value表示合成价格
scanf("%d",&total_mixture);
for(int i=0;i<total_mixture;i++)
{
scanf("%s %d:",equip_name,&consume_value);
mixture[i].name=equip_name;
mixture[i].value=consume_value;
mixture[i].num=0;
getchar();
while(true)
//下面利用getchar()输入材料名称。这里的处理比较繁琐，相信有更好的解决方案。
{
int need_num;
//need_num每种装备需要的数量
bool check_noword=false;
//判断当前混合装备是否不需要材料。
for(int j=0;;j++)
{
equip_name[j]=getchar();
if(equip_name[0]=='\n')
{
check_noword=true;
break;
}
if(equip_name[j]==' ')
{
equip_name[j]='\0';
break;
}
}
if(check_noword)
break;
scanf("%d",&need_num);
mixture[i].need_name[mixture[i].num]=equip_name;
mixture[i].need_num[mixture[i].num]=need_num;
mixture[i].num++;
if(getchar()=='\n')
break;
else
getchar();
}
}
}
void input_consume_info()
//输入消耗型装备信息
{
char equip_name[NAMESIZE];
//装备的名称
int equip_value;
//装备的价值
scanf("%d",&total_consume);
for(int i=0;i<total_consume;i++)
{
scanf("%s %d",equip_name,&equip_value);
consume[i].name=equip_name;
consume[i].value=equip_value;
consume[i].num=0;
}
}
void operation()
{
int m;
scanf("%d",&m);
char op[NAMESIZE+2];
for(int i=0;i<m;i++)
{
scanf("%s",op);
if(op[0]=='+')
add_equip(op+1);
else
delete_equip(op+1);
}
}
int cmp(const void* m,const void* n)
//将字符串由小到大排序
{
return strcmp((char*)m,(char*)n);
}
int Case=1;
void output()
{
printf("Case %d:\n%d\n%d\n",Case++,total_gold,total_room);
qsort(list_equipment,total_room,sizeof(list_equipment[0]),cmp);
//排序
for(int i=0;i<total_room;i++)
{
pair<int,int> equip_type_info=get_type(list_equipment[i]);
if(equip_type_info.first==3)
//如果是消耗型装备，则输出其数量。
printf("%s: %d\n",&list_equipment[i],consume[equip_type_info.second].num);
else
printf("%s: 1\n",&list_equipment[i]);
}
printf("\n");
}
int main()
{
while(~scanf("%d",&total_normal))
{
init();
input_normal_info();
input_mixture_info();
input_consume_info();
operation();
output();
}
}
测试数据
2 ring 1 sword 2 1 knife 3: 1 medicine 1 8 +100 +ring +ring +ring +ring +ring +sword +knife 2 ring 1 sword 2 1 knife 3: ring 2, sword 2 1 medicine 1 6 +100 +ring +ring +sword +sword +knife 2 ring 1 sword 2 1 knife 3: ring 2, sword 2 1 medicine 1 5 +100 +ring +ring +sword +knife 2 ring 1 sword 2 2 knife 3: ring 1, sword 1 kkk 3: ring 1, sword 1 1 medicine 1 9 +100 +ring +ring +ring +ring +sword +sword +knife +kkk 2 ring 1 sword 2 2 knife 3: ring 1, sword 1 kkk 2: knife 2, sword 1 1 medicine 1 9 +100 +ring +ring +sword +sword +knife +knife +sword +kkk 2 ring 1 sword 2 2 knife 3: ring 1, sword 1 kkk 2: knife 2, sword 1 1 medicine 1 10 +100 +ring +ring +sword +sword +knife +knife +sword +kkk -kkk 2 ring 1 sword 2 2 knife 3: ring 1, sword 1 kkk 2: knife 2, medicine 2 1 medicine 1 11 +100 +ring +ring +sword +sword +knife +knife +medicine +medicine +medicine +kkk 2 ring 1 sword 2 2 knife 3: ring 1, sword 1 kkk 2: knife 2, medicine 2 1 medicine 1 12 +100 +ring +ring +sword +sword +knife +knife +medicine +medicine +medicine +kkk -kkk 2 ring 1 sword 2 2 knife 3: ring 1, sword 1 kkk 2: knife 2, medicine 2 1 medicine 1 10 +100 +ring +ring +sword +sword +knife +knife +medicine +medicine +kkk 2 ring 1 sword 2 2 knife 3: ring 1, sword 1 kkk 2: knife 2, medicine 2 1 medicine 1 20 +100 +ring +ring +sword +sword +knife +knife +medicine +medicine +kkk +100 +ring +ring +sword +sword +knife +knife +medicine +medicine +kkk 2 ring 1 sword 2 2 knife 3: ring 1, sword 1 kkk 2: knife 2, medicine 2 1 medicine 1 21 +100 +ring +ring +sword +sword +knife +knife +medicine +medicine +medicine +kkk +100 +ring +ring +sword +sword +knife +knife +medicine +medicine +kkk 2 ring 1 sword 2 1 knife 3: medicine 1 1 medicine 1 8 +100 +ring +ring +ring +ring +ring +medicine +knife 2 ring 1 sword 2 1 knife 3: medicine 1 1 medicine 1 9 +100 +ring +ring +ring +ring +medicine +medicine +ring +knife
”杭电的测试数据中有用消耗型装备充当材料的情况，并且考虑到了“装备栏满时，消耗型装备数量大于合成需求量导致无法空出装备栏，结果没地方给合成装备”这样的情形。“
测过了，HDOJ的数据里没有将消耗型装备作为合成装备的材料的数据
[…] C Defend Jian Ge (HDU 4269) 模拟 http://zhyu.me/acm/hdu-4269.html http://hi.baidu.com/buaa_babt/item/a42588e604155b1f570f1db4 http://blog.csdn.net/acceptedxukai/article/details/7959708 http://lujunda.tk/2012/09/09/hdu4269%E6%A8%A1%E6%8B%9F-defend-jian-ge/ […]