【POJ C++题目】魔兽世界之一：备战

一、题目描述

描述

魔兽世界的西面是红魔军的司令部，东面是蓝魔军的司令部。两个司令部之间是依次排列的若干城市。
红司令部，City 1，City 2，……，City n，蓝司令部

两军的司令部都会制造武士。武士一共有 dragon 、ninja、iceman、lion、wolf 五种。每种武士都有编号、生命值、攻击力这三种属性。

双方的武士编号都是从1开始计算。红方制造出来的第n个武士，编号就是n。同样，蓝方制造出来的第n个武士，编号也是n。

武士在刚降生的时候有一个生命值。

在每个整点，双方的司令部中各有一个武士降生。

红方司令部按照iceman、lion、wolf、ninja、dragon的顺序循环制造武士。

蓝方司令部按照lion、dragon、ninja、iceman、wolf的顺序循环制造武士。

制造武士需要生命元。

制造一个初始生命值为m的武士，司令部中的生命元就要减少m个。

如果司令部中的生命元不足以制造某个按顺序应该制造的武士，那么司令部就试图制造下一个。如果所有武士都不能制造了，则司令部停止制造武士。

给定一个时间，和双方司令部的初始生命元数目，要求你将从0点0分开始到双方司令部停止制造武士为止的所有事件按顺序输出。
一共有两种事件，其对应的输出样例如下：

武士降生
输出样例： 004 blue lion 5 born with strength 5,2 lion in red headquarter
表示在4点整，编号为5的蓝魔lion武士降生，它降生时生命值为5，降生后蓝魔司令部里共有2个lion武士。（为简单起见，不考虑单词的复数形式）注意，每制造出一个新的武士，都要输出此时司令部里共有多少个该种武士。
司令部停止制造武士
输出样例： 010 red headquarter stops making warriors
表示在10点整，红方司令部停止制造武士

输出事件时：

首先按时间顺序输出；

同一时间发生的事件，先输出红司令部的，再输出蓝司令部的。

输入

第一行是一个整数，代表测试数据组数。

每组测试数据共两行。

第一行：一个整数M。其含义为，每个司令部一开始都有M个生命元( 1 <= M <= 10000)。

第二行：五个整数，依次是 dragon 、ninja、iceman、lion、wolf 的初始生命值。它们都大于0小于等于10000。

输出

对每组测试数据，要求输出从0时0分开始，到双方司令部都停止制造武士为止的所有事件。
对每组测试数据，首先输出"Case:n" n是测试数据的编号，从1开始。
接下来按恰当的顺序和格式输出所有事件。每个事件都以事件发生的时间开头，时间以小时为单位，有三位。

样例输入

1
2
3

1
20
3 4 5 6 7

样例输出

Case:1
000 red iceman 1 born with strength 5,1 iceman in red headquarter
000 blue lion 1 born with strength 6,1 lion in blue headquarter
001 red lion 2 born with strength 6,1 lion in red headquarter
001 blue dragon 2 born with strength 3,1 dragon in blue headquarter
002 red wolf 3 born with strength 7,1 wolf in red headquarter
002 blue ninja 3 born with strength 4,1 ninja in blue headquarter
003 red headquarter stops making warriors
003 blue iceman 4 born with strength 5,1 iceman in blue headquarter
004 blue headquarter stops making warriors

二、简要思路

数据结构

定义两个类，一个类是武士类Warrior，另一个类是指挥部类Command，Warrior类再派生出五个类：Dragon类、Ninja类、Iceman类、Lion类、Wolf类。在基类Warrior中定义虚函数，用以实现多态。虽然完成本题目不需要派生，但是为了以后的扩充方便，而且不同武士有不同的特点，我还是选择了派生这种结构方式。

Command类不适宜派生出red类和blue类，因为无论是red还是blue，所有的属性都是一致的，因此不适宜派生，直接定义Command red和blue就好了。red和blue的武士制造顺序不同，我们可以用一个数组来记录武士的顺序。同时，red和blue的武士总数量和各种武士数量都是不同的，我们可以用一个数组来记录数量。为了方便阅读和修改程序，我定义了一个枚举类型，并且规定0号位是武士总数之含义：enum warrior{total=0, dragon, ninja, iceman, lion, wolf};，这个就是我默认的武士序号了，这样在使用数组的时候就可以表示成例如WarriorNumber[dragon]或者WarriorOrder[wolf]这种方式了，增加了程序的可阅读性。

我们用初始生命值名字（字符串）初始化red对象和blue对象以及各种武士对象，并且将其设为私有成员变量。所有成员函数都是公有成员。定义一个Warrior类指针数组，用来存放不同派生类的地址，存放顺序与枚举类型定义的相同。这个指针在访问成员函数时的语句就实现多态了。

初步实现想法

这道题主要难点不在于面向对象编程，而在于：

如果Command部中的生命元不足以制造某个按顺序应该制造的武士，那么Command部就试图制造下一个。

以及，如果当某个Command部的所有武士都不能制造，但另一个部却还能制造的时候，如何让这个部不再输出结果。

写一个尝试制造武士的成员函数，循环遍历制造顺序的数组，每访问一个元素就试试能不能制造，若能则返回这个武士的序号；若不能则继续前进，访问下一个元素，看看行不行，最终肯定能找到一个可以制造的武士。在主函数要用循环变量i控制制造顺序的数组下标，每循环一次，就访问数组元素一次。

要注意，red和blue不能共用同一个循环变量i，因为会出现这种可能情况：比如i=3，red方已经有不能制造的武士，但blue方还没有不能制造的武士。那red方就要开始循环遍历制造顺序的数组，成员函数返回的i=5。blue返回的函数值是i=3，那就不一样了。

为什么说最终肯定能找到一个可以制造的武士呢？因为我在尝试制造武士之前，还要执行一个是否停止制造武士的成员函数，判断我这个部能不能制造武士，如果一个也制造不了，那么就要宣布停止制造了。如何实现这个函数？自然，当我Command部的总生命值都小于制造各种武士所需要的的生命值，那就肯定不能制造了。否则，还是可以制造。当这个函数说还是可以继续制造的时候，我们再去执行尝试制造武士的成员函数，那肯定能找到可以制造的武士了。

当Command部再也不能制造武士的时候，就要宣布“不能制造”了。同时我设置了一个bool变量Start，这个变量用来记录Command部有无进行制造，如果Start=0，表示我已经停止制造了，后面的循环你不要再与我部扯上关系。如果是1，那么可以继续制造、输出。

什么时候停止呢？就是当双方start都为0的时候，循环停止，释放内存，程序结束。

三、自己的初步代码

这只是一个初步的代码，很显然还有很多可以改进的地方（另外为了便于调试程序，我的程序输入和输出均与题目要求暂时不符）：

#include <iostream>
#include <string>
#include <iomanip>
#include <ctime> 
using namespace std;
const int Warrior_num = 5;
enum warrior{total=0, dragon, ninja, iceman, lion, wolf};
//1dragon 2ninja 3iceman 4lion 5wolf 

//No.0
class Warrior{
	protected:
		int HP;
		string Name;
	public:
		virtual int getHP() {return HP;}
		virtual string getName() {return Name;}
		//virtual void createWarrior();
};

//No.1
class Dragon:public Warrior{
	public:
		Dragon(const int _HP) { HP=_HP; Name="dragon"; }
};

//No.2
class Ninja:public Warrior{
	public:
		Ninja(const int _HP){ HP=_HP; Name="ninja"; }
};

//No.3
class Iceman:public Warrior{
	public:
		Iceman(const int _HP){ HP=_HP; Name="iceman"; }
};

//No.4
class Lion:public Warrior{
	public:
		Lion(const int _HP){ HP=_HP; Name="lion"; }
};

//No.5
class Wolf:public Warrior{
	public:
		Wolf(const int _HP){ HP=_HP; Name="wolf"; }
};

//====================================================
class Command{
	private:
		string Name;
		int HP;
		int WarriorNumber[Warrior_num+1];//记录总数以及每个武士的数量 
		//Warrior *p[200]; 
	public:
		static int time;//游戏系统时间 
		short Order[Warrior_num+1];//制造武士的顺序记录 
		Command(string _Name, const short _Order[], const int _HP);
		void MakeWarrior(Warrior *p[], int i);
		void StopMakeWarrior();
		int FindMakeWarrior(Warrior *p[], int &i);
		bool isStopMakeWarrior(short dm, short nm, short im, short lm, short wm);
		int getHP() {return HP;}
		string getName(){return Name;}
};
int Command::time = -1;

Command::Command(string _Name, const short _Order[], const int _HP):Name(_Name), HP(_HP) 
{ 
	for(int i=0; i<=Warrior_num; i++) 
	{
		Order[i] = _Order[i];
		WarriorNumber[i] = 0;
	}
}

int Command::FindMakeWarrior(Warrior *p[], int &i)//返回可以生成武士的序号 
{
	if (HP >= p[Order[i]]->getHP()) return i; 
		else do{
			i++;
			if(i==6) i=1;
		}while(HP < p[Order[i]]->getHP());
	return i;
} 

bool Command::isStopMakeWarrior(short dm, short nm, short im, short lm, short wm)
{
	return ( HP<dm && HP<nm && HP<im && HP<lm && HP<wm );//返回1：不能再制造任何武士了 
}

void Command::MakeWarrior(Warrior *p[], int i)
{
	short ord = Order[i];
	HP -= p[ord]->getHP();
	WarriorNumber[total]++;
	WarriorNumber[ord]++;
	cout<<setw(3)<<setfill('0')<<time<<" "<<getName()<<" "<<p[ord]->getName()<<" "<<WarriorNumber[total]<<" born with strength "<<p[ord]->getHP()
		<<", "<<WarriorNumber[ord]<<" "<<p[ord]->getName()<<" in "<<getName()<<" headquarter"<<", rest HP = "<<HP<<endl;
}

void Command::StopMakeWarrior()
{
	cout<<setw(3)<<setfill('0')<<time<<" "<<Name<<" headquarter stops making warriors"<<endl;
}

int main()
{
	int n=1;
	short M, dm, nm, im, lm, wm;
	short redOrder[Warrior_num+1]={0, iceman, lion, wolf, ninja, dragon};
	short blueOrder[Warrior_num+1]={0, lion, dragon, ninja, iceman, wolf};
	//cin>>n;
	cin>>M;//输入生命元 
	cin>>dm>>nm>>im>>lm>>wm;
	clock_t startTime, endTime;
	startTime = clock();
	Command red("red", redOrder, M), blue("blue", blueOrder, M);
	Warrior *p[Warrior_num+1] = {new Warrior, new Dragon(dm), new Ninja(nm), new Iceman(im), new Lion(lm), new Wolf(wm)};
	while(n--)
	{
		int i=0, j=0;
		bool redStart = 1, blueStart = 1;
		Command::time = -1;
		while(redStart || blueStart)
		{
			i++; j++;//两个循环变量
			if(i==6) i=1;
			if(j==6) j=1;
			Command::time ++;
			if(redStart && red.isStopMakeWarrior(dm, nm, im, lm, wm)) {red.StopMakeWarrior(); redStart=0;}
			if(redStart) red.MakeWarrior(p, red.FindMakeWarrior(p, i));	
			if(blueStart && blue.isStopMakeWarrior(dm, nm, im, lm, wm)) {blue.StopMakeWarrior(); blueStart=0;}
			if(blueStart) blue.MakeWarrior(p, blue.FindMakeWarrior(p, j));
			cout<<endl;
		}
	}
	for(int i=0; i<=5; i++) delete p[i];
	endTime = clock();
	cout<<"time:"<<(double)(endTime - startTime) <<"ms"<<endl;
	return 0;
}

输入1：

1 2	400 20 3 300 60 98

输出1：

000 red iceman 1 born with strength 300, 1 iceman in red headquarter, rest HP = 100
000 blue lion 1 born with strength 60, 1 lion in blue headquarter, rest HP = 340

001 red lion 2 born with strength 60, 1 lion in red headquarter, rest HP = 40
001 blue dragon 2 born with strength 20, 1 dragon in blue headquarter, rest HP = 320

002 red ninja 3 born with strength 3, 1 ninja in red headquarter, rest HP = 37
002 blue ninja 3 born with strength 3, 1 ninja in blue headquarter, rest HP = 317

003 red dragon 4 born with strength 20, 1 dragon in red headquarter, rest HP = 17
003 blue iceman 4 born with strength 300, 1 iceman in blue headquarter, rest HP = 17

004 red ninja 5 born with strength 3, 2 ninja in red headquarter, rest HP = 14
004 blue ninja 5 born with strength 3, 2 ninja in blue headquarter, rest HP = 14

005 red ninja 6 born with strength 3, 3 ninja in red headquarter, rest HP = 11
005 blue ninja 6 born with strength 3, 3 ninja in blue headquarter, rest HP = 11

006 red ninja 7 born with strength 3, 4 ninja in red headquarter, rest HP = 8
006 blue ninja 7 born with strength 3, 4 ninja in blue headquarter, rest HP = 8

007 red ninja 8 born with strength 3, 5 ninja in red headquarter, rest HP = 5
007 blue ninja 8 born with strength 3, 5 ninja in blue headquarter, rest HP = 5

008 red ninja 9 born with strength 3, 6 ninja in red headquarter, rest HP = 2
008 blue ninja 9 born with strength 3, 6 ninja in blue headquarter, rest HP = 2

009 red headquarter stops making warriors
009 blue headquarter stops making warriors

time:239ms

输入2：

1 2	30 40 50 60 70 80

输出2：

000 red headquarter stops making warriors
000 blue headquarter stops making warriors

time:5ms

输入3：

1 2	40 3 4 5 6 7

输出3：

000 red iceman 1 born with strength 5, 1 iceman in red headquarter, rest HP = 35
000 blue lion 1 born with strength 6, 1 lion in blue headquarter, rest HP = 34

001 red lion 2 born with strength 6, 1 lion in red headquarter, rest HP = 29
001 blue dragon 2 born with strength 3, 1 dragon in blue headquarter, rest HP = 31

002 red wolf 3 born with strength 7, 1 wolf in red headquarter, rest HP = 22
002 blue ninja 3 born with strength 4, 1 ninja in blue headquarter, rest HP = 27

003 red ninja 4 born with strength 4, 1 ninja in red headquarter, rest HP = 18
003 blue iceman 4 born with strength 5, 1 iceman in blue headquarter, rest HP = 22

004 red dragon 5 born with strength 3, 1 dragon in red headquarter, rest HP = 15
004 blue wolf 5 born with strength 7, 1 wolf in blue headquarter, rest HP = 15

005 red iceman 6 born with strength 5, 2 iceman in red headquarter, rest HP = 10
005 blue lion 6 born with strength 6, 2 lion in blue headquarter, rest HP = 9

006 red lion 7 born with strength 6, 2 lion in red headquarter, rest HP = 4
006 blue dragon 7 born with strength 3, 2 dragon in blue headquarter, rest HP = 6

007 red ninja 8 born with strength 4, 2 ninja in red headquarter, rest HP = 0
007 blue ninja 8 born with strength 4, 2 ninja in blue headquarter, rest HP = 2

008 red headquarter stops making warriors
008 blue headquarter stops making warriors

time:81ms

花的时间比较长，这个程序的优化之路还是任重而道远啊！

8.1稍微简化了一下这个程序，主要的改动是合并了一些成员函数，并声明类Command为类Warrior的友元：

#include <iostream>
#include <string>
#include <iomanip>
#include <ctime>
using namespace std;
const int WARRIOR_NUM = 5;
enum warrior{total=0, dragon, ninja, iceman, lion, wolf};
short M, dm, nm, im, lm, wm;
//1dragon 2ninja 3iceman 4lion 5wolf 

//No.0
class Warrior{
	protected:
		int HP;
		string Name;
	public:
		friend class Command;
		virtual int getHP() {return HP;}
		virtual string getName() {return Name;}
		//virtual void createWarrior();
};

//No.1
class Dragon:public Warrior{
	public:
		Dragon(const int _HP) { HP=_HP; Name="dragon"; }
};

//No.2
class Ninja:public Warrior{
	public:
		Ninja(const int _HP){ HP=_HP; Name="ninja"; }
};

//No.3
class Iceman:public Warrior{
	public:
		Iceman(const int _HP){ HP=_HP; Name="iceman"; }
};

//No.4
class Lion:public Warrior{
	public:
		Lion(const int _HP){ HP=_HP; Name="lion"; }
};

//No.5
class Wolf:public Warrior{
	public:
		Wolf(const int _HP){ HP=_HP; Name="wolf"; }
};

//====================================================
class Command{
	private:
		string Name;
		short OrderCount;
		int HP;
		int WarriorNumber[WARRIOR_NUM+1];//记录总数以及每个武士的数量 
		//Warrior *p[200]; 
	public:
		static int time;//游戏系统时间 
		short Order[WARRIOR_NUM+1];//制造武士的顺序记录 
		Command(string _Name, const short _Order[], const int _HP);
		bool CreateWarrior(Warrior *p[]);
		void StopCreateWarrior();
		int getHP() {return HP;}
		string getName(){return Name;}
};
int Command::time = -1;

Command::Command(string _Name, const short _Order[], const int _HP):Name(_Name), HP(_HP) 
{ 
	OrderCount = 1;
	for(int i=0; i<=WARRIOR_NUM; i++) 
	{
		Order[i] = _Order[i];
		WarriorNumber[i] = 0;
	}
}

bool Command::CreateWarrior(Warrior *p[])
{
	if( HP<dm && HP<nm && HP<im && HP<lm && HP<wm ) return 0;
	while(HP < p[Order[OrderCount]]->HP)
	{
			OrderCount++;
			if(OrderCount==6) OrderCount=1;
	}
	short ord = Order[OrderCount];
	HP -= p[ord]->HP;
	WarriorNumber[total]++;
	WarriorNumber[ord]++;
	cout<<setw(3)<<setfill('0')<<time<<" "<<this->Name<<" "<<p[ord]->Name<<" "<<WarriorNumber[total]<<" born with strength "<<p[ord]->HP
		<<", "<<WarriorNumber[ord]<<" "<<p[ord]->Name<<" in "<<this->Name<<" headquarter"<<", rest HP = "<<this->HP<<endl;
	OrderCount++;
	if(OrderCount==6) OrderCount=1;
	return 1;
}

void Command::StopCreateWarrior()
{
	cout<<setw(3)<<setfill('0')<<time<<" "<<this->Name<<" headquarter stops making warriors"<<endl;
}

int main()
{
	int n=1;
	short redOrder[WARRIOR_NUM+1]={0, iceman, lion, wolf, ninja, dragon};
	short blueOrder[WARRIOR_NUM+1]={0, lion, dragon, ninja, iceman, wolf};
	//cin>>n;
	cin>>M;//输入生命元 
	cin>>dm>>nm>>im>>lm>>wm;
	clock_t startTime, endTime;
	startTime = clock();
	Command red("red", redOrder, M), blue("blue", blueOrder, M);
	Warrior *p[WARRIOR_NUM+1] = {new Warrior, new Dragon(dm), new Ninja(nm), new Iceman(im), new Lion(lm), new Wolf(wm)};
	while(n--)
	{
		bool redCreate = 1, blueCreate = 1;
		Command::time = -1;
		while(redCreate || blueCreate)
		{
			Command::time ++;
			if(redCreate == 1)
				if(red.CreateWarrior(p) == 0){redCreate = 0; red.StopCreateWarrior();} 
			if(blueCreate == 1)
				if(blue.CreateWarrior(p) == 0){blueCreate = 0; blue.StopCreateWarrior();} 
			cout<<endl;
		}
	}
	for(int i=0; i<=5; i++) delete p[i];
	endTime = clock();
	cout<<"time:"<<(double)(endTime - startTime) <<"ms"<<endl;
	return 0;
}