离散优化算法大作业——2021华为软件精英挑战赛初赛赛题

离散优化算法大作业报告

问题描述

我选择解决的问题是2021年华为软件精英挑战赛的初赛，这是一个虚拟机调度与迁移问题。

问题要点概括如下：

• 服务器：我们有一系列服务器可以选择，这些服务器的CPU核数、内存大小、硬件成本（购买成本）、每日能耗成本（运行成本）各不相同。此外，服务器采用NUMA架构，这意味着服务器的资源是平均分配在两个节点A和B上的。
• 虚拟机：虚拟机是分配给用户的，根据型号不同，每一台虚拟机需要分配一定的CPU核数和内存大小；虚拟机也分为单节点部署和双节点部署，单节点部署意味着虚拟机要部署在某一台服务器的A节点或B节点上；双节点部署也将CPU核数和内存大小平均分配在某一台服务器的两个节点上。
• 用户请求：每一天会接受一系列用户的请求（包括增加虚拟机和删除已有虚拟机），增加虚拟机要将虚拟机分配到已有的服务器或者新购买的服务器上，要确保容量足够；而删除虚拟机则是根据虚拟机编号将其删除，同时释放占据的空间。
• 可以进行的操作：有购买服务器，分配虚拟机和虚拟机迁移；购买服务器就是添置新的服务器，同时要花费硬件成本；分配虚拟机就是将用户的add请求分配到已有的或者新购买的服务器上；虚拟机迁移是指在每天进行分配之前，可以对现存虚拟机进行迁移，包括从一台服务器迁移到另一台服务器，或者从一个节点迁移到另一个节点，迁移不消耗成本。
• 成本计算：总成本是硬件成本和能耗成本的加和。每购买一台服务器，就要花费一定的硬件成本；而已购买的服务器每运行一天，就要花费每日能耗成本（如果服务器上没有安排虚拟机，就不必开启，也就没有能耗成本）。在解可行的前提下，总成本越小越好。

问题分析和算法设计

按下输入输出、类的构建、实现细节等等不谈，我们需要实现的算法实际上就是三个部分：

1. 虚拟机分配方案：对于一个虚拟机添加请求，如何选择它放置的服务器。
2. 服务器购买方案：包括何时购买以及购买哪种类型。
3. 虚拟机迁移方案：何时迁移，迁移哪些虚拟机，迁移到哪里去。

下面我将具体谈一谈这三个部分的思考过程和实现方案。

虚拟机分配方案

将虚拟机分配到现有的服务器上，这类似于一个装箱问题。在实现中，我考虑了First-Fit算法和Best-Fit算法，比较后选择了Best-Fit算法，也就是对分配到现有的每一个服务器的效果进行估值。我们希望目标服务器与待部署虚拟机的大小尽可能接近，因此对剩余的（cpuCores，memorySize）进行评估，希望它们越小越好。

在评估函数的选择上，一开始使用的是直接相加，即用c+m进行估值；后来发现cpuCores和memorySize两个维度的填充率差别较大，cpu总是填充得比较满，所以调高了cpu的权重，改为0.75*c+0.25*m；；后来考虑到当剩余空间很小时价格也会变得很低，所以改线性相加为平方相加，并枚举参数检验效果，最终选择了3*c^2+m^2作为估值函数，在几种估值函数中效果最好。

在评估时，还要考虑到，如果目标服务器是一个空服务器（没有挂载其他虚拟机），那么就要打开它，使能耗成本增加。在这种情况下，设置一个额外的惩罚，即在估值结果上*1.4。

在实现上，枚举每个服务器，然后计算估值，取估值最小者作为目标服务器。

服务器购买方案

由于服务器购买必然要花费硬件成本，而硬件成本是比较大的，所以我尽量不去购买新的服务器，也就是先尽可能在现有的服务器中安排，如果任何一台现有服务器都不能满足需要，再去购买新的服务器。

在服务器购买上，我考虑了几种方案：

1. 按成本排序，又可以分为是按硬件成本排序还是按能耗成本排序，或者综合考虑两个成本。希望找到成本最小的服务器进行购买。
2. 找到最匹配服务器，考虑和虚拟机分配类似的方法，按照Best-Fit算法找到最适服务器进行购买。

如果使用单一方法，在我的测试中，按能耗成本排序，然后找到能装得下的每日能耗最小的服务器进行购买是最优的。这是因为如果服务器开启的时间很长，能耗成本会远远超过硬件成本；也会超过不匹配带来的影响。

但是很显然地，前期购买的服务器会消耗更大的能耗成本；而后期购买的服务器，能耗成本就影响不大了。特别地，最后一天购买的服务器只运行一天，也就只有一天的能耗成本。所以我考虑将上面的方法结合起来，在前期找到成本最小的服务器进行购买，在后期则希望服务器和虚拟机尽量匹配，也就是使用Best-Fit算法。

经过测试不同组合和不同分界天数，发现前20%天采用能耗成本最小方案；之后采用最适服务器方案，效果最好。

虚拟机迁移方案

首先要考虑，为什么要进行虚拟机迁移？我认为是如下的原因：原有的虚拟机在删除后，占用的空间被释放，就出现了很多碎片。考虑一个极端的例子，将每一台服务器上的虚拟机都删除到只剩一个，如果不进行迁移，就会浪费很多空间，花费很多不必要的运行成本。因此我的迁移方案从这个角度出发，希望关闭剩余虚拟机比较少的服务器，减少能耗成本。

具体操作如下：将各个服务器按照剩余空间的比例从大到小排列，这样，最开始的服务器就处于”将空“状态，从头开始遍历服务器，尝试将这些服务器上的虚拟机迁移到其他非空服务器上。寻找目标服务器的过程类似于虚拟机分配方案，采用Best-Fit算法找最适合的服务器。注意，如果找到的最适服务器就是当前服务器，则不进行迁移。

结果评估

采用自动评分器进行评估，测试集为给定的两个training-data，并根据结果不断改善代码方案以及调整参数。

最终的结果如下：

心得体会

问题建模方面

对实际问题如何用转化到算法问题有了更深的体会，对一个复杂问题能够找到关键信息，分解成几个需要解决的小问题；并且提高了处理较为复杂的输入输出并转化成便于使用的信息的能力。

算法设计方面

体会到了算法迭代升级的难点和乐趣。在入手这个问题时，我先尝试构建了一个”可行解“，也就是First-Fit分配+购买第一个服务器+无迁移，主要是为了测试输入输出，之后的算法在此基础上进行迭代升级。但是经常遇到有些功能在此之前没有定义，例如类中少了一个需要的对象之类的，然后就要重头改起，十分麻烦。再比如服务器购买问题，由于一天中新的服务器编号是一类一起编号的，而我们选择时是根据虚拟机选择对应服务器，同类并不相邻。所以在购买服务器时要进行重标号，这也是一个比较难处理的细节。在解决这些问题的过程中，debug能力提升了不小。

还常常会遇到超时的情况，明明感觉这种方法用不了太长时间，但时间消耗却出乎意料。对于这样的问题，我在许多地方设置了时间戳，可以看到每一个部分运行的时间大小，对于占比较大的部分进行优化。例如我发现迁移函数总是用时很长，然后就对它进行分解，发现排序的过程占比很大，但是根据时间复杂度来说并不应该这么长，分析发现是不断地查哈希表用时太久，就通过预先构建下标数组+空间占用率的方式来减少了这一时间消耗。

还有不同算法之间的选择问题，不同参数的调整问题……解决这些问题的过程很痛苦，但最后看到成本一点点降低确实很有成就感。

完整代码

//一次性读入所有输入，并存到类中
//遇到需求优先使用已有的服务器（根据BestFit算法找到最适服务器）
//当服务器不够用时，购买一个新的服务器
//在购买服务器上，综合考虑成本和匹配程度
//细节问题：当天购买的服务器编号未必是逐个递增的，例如先买了a，编号为0，然后买了b，b的编号未必为1，因为如果后面又买了a，b的编号也要向后移
//当第二次购买a时，插入到allServers中，然后要对后面的所有addOption进行更新
//在为虚拟机分配服务器上，视为装箱问题解决，使用Best-Fit算法
//估值函数定为3*c^2+m^2,c和m为剩余核数和内存
//迁移函数是为了整理服务器上的虚拟机，把vm从快空的server迁走以节省电费
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
#include<string>
#include<algorithm>
#include<numeric>
#include<cmath>
using namespace std;

struct server//服务器类
{
    string model;
    int cpuCores = 0;
    int memorySize = 0;
    long hardwareCost = 0;
    long energyCostPerDay = 0;
};

struct virtualMachine//虚拟机类
{
    string model;
    int cpuCores = 0;
    int memorySize = 0;
    bool isDoubleNode = 0;
};

struct serverInfo//已购买的所有服务器信息
{
    string model; //型号
    int A_cpu; //AB节点剩余的核数和内存大小
    int A_Memory;
    int B_cpu;
    int B_Memory;
    long energyCostPerDay;
    bool inUse;//是否在使用中
    unordered_set<int> vmId;
};

struct operation//操作信息
{
    string type;// add or del
    string model;// 虚拟机型号
    int id = 0;// 操作的虚拟机id
};

struct addOption//进行增加操作的信息，用于输出
{
    string model;
    int id;
    int serverID;      //存放的serverId
    bool isDoubleNode; //是否使用双节点部署
    bool isA = true;         //true代表存放在A节点中，false代表存放在B节点中
};

unordered_map<string, server> serverMap;//服务器型号信息记录
unordered_map<string, virtualMachine> vmMap;//虚拟机型号信息记录
vector<string> serverList;//服务器列表，用于排序
vector<int> TimesOfDay;//记录每天的请求数目
vector<operation> allOperations;//记录所有请求
vector<serverInfo> allServers;//记录已经拥有的所有服务器信息
//unordered_map<int, bool> vmInfo;//记录虚拟机id以及是否被删除
unordered_map<int, addOption> addResult;//保留每一次add的结果
int vmNum = 0;
void readData()//直接读取所有信息，包括服务器型号、虚拟机型号、每日请求
{
	//获取服务器型号，存入哈希表
	int N;
	cin >> N;
	cin.ignore();
	for (int i = 0; i < N; ++i)
	{
		string serverStream;
		server serverData;
		getline(cin, serverStream);
		int pos = 1;
		for (; serverStream[pos] != ','; ++pos)//型号
			serverData.model += serverStream[pos];
		while (!isdigit(serverStream[pos])) ++pos;//定位到下一个数字
		for (; isdigit(serverStream[pos]); ++pos)//cpu核数
			serverData.cpuCores = serverData.cpuCores * 10 + serverStream[pos] - '0';
		while (!isdigit(serverStream[pos])) ++pos;//定位到下一个数字
		for (; isdigit(serverStream[pos]); ++pos)//内存大小
			serverData.memorySize = serverData.memorySize * 10 + serverStream[pos] - '0';
		while (!isdigit(serverStream[pos])) ++pos;//定位到下一个数字
		for (; isdigit(serverStream[pos]); ++pos)//硬件成本
			serverData.hardwareCost = serverData.hardwareCost * 10 + serverStream[pos] - '0';
		while (!isdigit(serverStream[pos])) ++pos;//定位到下一个数字
		for (; isdigit(serverStream[pos]); ++pos)//每日能耗成本
			serverData.energyCostPerDay = serverData.energyCostPerDay * 10 + serverStream[pos] - '0';
		serverMap[serverData.model] = serverData;
		serverList.push_back(serverData.model);
	}
	//获取虚拟机型号，存入哈希表
	int M;
	cin >> M;
	cin.ignore();
	for (int i = 0; i < M; ++i)
	{
		string VMStream;
		virtualMachine VMData;
		getline(cin, VMStream);
		int pos = 1;
		for (; VMStream[pos] != ','; ++pos)
			VMData.model += VMStream[pos];
		while (!isdigit(VMStream[pos])) ++pos;//定位到下一个数字
		for (; isdigit(VMStream[pos]); ++pos)//cpu核数
			VMData.cpuCores = VMData.cpuCores * 10 + VMStream[pos] - '0';
		while (!isdigit(VMStream[pos])) ++pos;//定位到下一个数字
		for (; isdigit(VMStream[pos]); ++pos)//内存大小
			VMData.memorySize = VMData.memorySize * 10 + VMStream[pos] - '0';
		while (!isdigit(VMStream[pos])) ++pos;//定位到下一个数字
		for (; isdigit(VMStream[pos]); ++pos)//是否双节点部署
			VMData.isDoubleNode = VMStream[pos] == '1';
		vmMap[VMData.model] = VMData;
	}
	//获取所有操作请求，将每日操作数存入TimesOfDay数组；操作内容存入allOperations数组
	int T;
	cin >> T;
	for (int i = 0; i < T; ++i)
	{
		int R;
		cin >> R;
		cin.ignore();
		TimesOfDay.push_back(R);
		for (int j = 0; j < R; ++j)
		{
			string opStream;
			operation opData;
			getline(cin, opStream);
			opData.type = opStream.substr(1, 3);
			if (opData.type == "add")
				opData.model = opStream.substr(6, opStream.find(',', 6) - 6);
			int pos = opStream.size() - 2;
			while (isdigit(opStream[pos - 1])) --pos;//找到id的开头
			opData.id = stoi(opStream.substr(pos, opStream.size() - 1 - pos));
			allOperations.push_back(opData);
		}
	}
}
void printAnswer(vector<pair<string, int>>& purchase,vector<addOption> &addAnswer,vector<string> &migrationAnswer)
{
	cout << "(purchase, " << purchase.size() << ")" << endl;
	for (auto& p : purchase)
		cout << "(" << p.first << ", " << p.second << ")" << endl;
	cout << "(migration," + to_string(migrationAnswer.size()) + ")" << endl;
	for (auto& s : migrationAnswer)
		cout << s << endl;
	for (int i = 0; i < addAnswer.size(); ++i)
	{
		string res = "(" + to_string(addAnswer[i].serverID);
		if (!addAnswer[i].isDoubleNode)
			res+=", ",res += (addAnswer[i].isA ? "A" : "B");
		res += ")";
		cout << res << endl;
	}
}
void migration(vector<string>& migrationAnswer)//虚拟机迁移函数，整理当前的服务器
{
	if (floor(vmNum * 5.0 / 1000) == 0)
		return;
	//clock_t time1 = clock(), time2, time3;
	double tryTime = 0;
	int migrationTimes = 0;//迁移总次数
	//通过捆绑下标和利用率进行排序，优化效率
	vector<pair<int,double>> indexOfServer(allServers.size());//服务器编号数组，用于排序
	for (int i = 0; i < allServers.size(); ++i)
		indexOfServer.push_back({ i,(allServers[i].A_cpu + allServers[i].B_cpu) * 1.0 / serverMap[allServers[i].model].cpuCores + (allServers[i].A_Memory + allServers[i].B_Memory) * 1.0 / serverMap[allServers[i].model].memorySize });
	sort(indexOfServer.begin(), indexOfServer.end(), [](auto& p1, auto& p2) {return p1.second > p2.second; });
	
	//time2 = clock();
	//cout << "sort time " << (double)(time2 - time1) / CLOCKS_PER_SEC << "s" << " ";
	int index = 0, cnt = 0;
	for (index = 0; index < indexOfServer.size(); ++index)//从前往后，尝试迁移走服务器上的所有虚拟机
	{
		//cout << index << endl;
		auto& serverOrigin = allServers[indexOfServer[index].first];
		if (serverOrigin.vmId.size() > 6 || serverOrigin.vmId.empty())//对没有虚拟机或者虚拟机个数>6的服务器，不尝试迁移
			continue;
		vector<int> indexOfVm(serverOrigin.vmId.begin(), serverOrigin.vmId.end());
		for (int vmIndex : indexOfVm)//对这台服务器上的每一台虚拟机，执行迁移
		{
			//time2 = clock();
			++cnt;
			auto& vmInfo = addResult[vmIndex];
			//auto& vmInfo = addResult[*serverOrigin.vmId.begin()];
			//迁移的过程类似于分配的过程，只不过如果分配失败无法购买新的
			double bestFit = INT_MAX;//bestFit的最小剩余
			bool findOne = false;//代表找到了一个合适的服务器
			int targetServer;
			bool isA = true;
			//遍历已有的服务器，判断是否满足需要
			auto& vm = vmMap[vmInfo.model];
			for (int serverId = 0; serverId < allServers.size(); ++serverId)//只能向后迁移
			{
				auto& target = allServers[serverId];
				if (target.vmId.empty())//不要迁移到已经空了的服务器上
					continue;
				if (vm.isDoubleNode == true)//双节点部署
				{
					int c = vm.cpuCores / 2, m = vm.memorySize / 2;
					if (target.A_cpu >= c && target.B_cpu >= c && target.A_Memory >= m && target.B_Memory >= m)//可行
					{
						double thisLeft = 3 * pow((target.A_cpu + target.B_cpu - c * 2), 2) + pow((target.A_Memory + target.B_Memory - m * 2), 2);
						if (thisLeft < bestFit)//计算分配后的价值是否小于当前最小剩余
							findOne = true, targetServer = serverId, bestFit = thisLeft;
					}
				}
				else
				{
					int c = vm.cpuCores, m = vm.memorySize;
					if (target.A_cpu >= c && target.A_Memory >= m)//能装下
					{
						double thisLeft = 3 * pow((target.A_cpu - c), 2) + pow((target.A_Memory - m), 2);
						if (thisLeft < bestFit)
							findOne = true, targetServer = serverId, isA = true, bestFit = thisLeft;
					}
					else if (target.B_cpu >= c && target.B_Memory >= m)
					{
						double thisLeft = 3 * pow((target.B_cpu - c), 2) + pow((target.B_Memory - m), 2);
						if (thisLeft < bestFit)
							findOne = true, targetServer = serverId, isA = false, bestFit = thisLeft;
					}
				}
			}
			if (findOne && targetServer != indexOfServer[index].first)//使用已有服务器，对服务器信息进行更新
			{
				//cout << index << " " << vmIndex << " " << targetServer <<" "<<vm.isDoubleNode << endl;
				//恢复origin服务器，类似del过程
				serverOrigin.vmId.erase(serverOrigin.vmId.find(vmInfo.id));
				if (serverOrigin.vmId.empty())
					serverOrigin.inUse = false;
				int c = vmMap[vmInfo.model].cpuCores, m = vmMap[vmInfo.model].memorySize;
				if (vmInfo.isDoubleNode)
					c /= 2, m /= 2;
				if (vmInfo.isDoubleNode)
				{
					serverOrigin.A_cpu += c;
					serverOrigin.B_cpu += c;
					serverOrigin.A_Memory += m;
					serverOrigin.B_Memory += m;
				}
				else if (vmInfo.isA)
				{
					serverOrigin.A_cpu += c;
					serverOrigin.A_Memory += m;
				}
				else
				{
					serverOrigin.B_cpu += c;
					serverOrigin.B_Memory += m;
				}
				//改变目标服务器，类似add过程
				allServers[targetServer].vmId.insert(vmInfo.id);
				allServers[targetServer].inUse = true;
				vmInfo.serverID = targetServer;
				if (vm.isDoubleNode == true)//双节点部署
				{
					int c = vm.cpuCores / 2, m = vm.memorySize / 2;
					allServers[targetServer].A_cpu -= c;
					allServers[targetServer].B_cpu -= c;
					allServers[targetServer].A_Memory -= m;
					allServers[targetServer].B_Memory -= m;
				}
				else if (isA)
				{
					vmInfo.isA = true;
					int c = vm.cpuCores, m = vm.memorySize;
					allServers[targetServer].A_cpu -= c;
					allServers[targetServer].A_Memory -= m;
				}
				else
				{
					vmInfo.isA = false;
					int c = vm.cpuCores, m = vm.memorySize;
					allServers[targetServer].B_cpu -= c;
					allServers[targetServer].B_Memory -= m;
				}
				string res="("+to_string(vmInfo.id)+","+to_string(vmInfo.serverID);
				if (!vmInfo.isDoubleNode)
					res += ",", res += (vmInfo.isA ? "A" : "B");
				res += ")";
				migrationAnswer.push_back(res);
				++migrationTimes;
				if (migrationTimes >= floor(vmNum * 5.0 / 1000))//达到迁移数目了，直接返回
					return;
			}
			//time3 = clock();
			//tryTime += (double)(time3 - time2) / CLOCKS_PER_SEC;
		}
	}
	//cout << floor(vmNum * 5.0 / 1000) << " " << migrationAnswer.size() << endl;
	//time2 = clock();
	//cout << "migration time " << (double)(time2 - time1) / CLOCKS_PER_SEC << "s" << " ";
	//cout << "尝试迁移虚拟机总数为：" << cnt <<",tryTime: "<<tryTime<< endl;
}
void solve()//对于每一条请求，给出解决方案
{
	int index = 0, day = 0;
	for (int times : TimesOfDay)//遍历每一天
	{
		++day;
		int beg = index, cnt = 0;//cnt记录寻找次数
		//clock_t startTime, endTime;
		double addTime = 0, delTime = 0, findTime = 0, buyTime = 0;
		//startTime = clock();
		//vector<int> indexOfServer(allServers.size());
		//iota(indexOfServer.begin(), indexOfServer.end(), 0);
		//sort(indexOfServer.begin(), indexOfServer.end(), [](int &a, int &b) {return allServers[a].A_cpu > allServers[b].A_cpu; });
		//endTime = clock();
		//cout << "The run time of sort of day " << day << " is:" << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
		unordered_map<string,int> purchase;//存放购买的服务器型号和数目
		vector<pair<string, int>> purchaseNum;//存放购买序列
		vector<string> migrationAnswer;//存放迁移的答案
		vector<addOption> addAnswer;
		migration(migrationAnswer);//执行迁移
		for (int i = 0; i < times; ++index, ++i)//遍历当天所有请求
		{
			auto op = allOperations[index];
			if (op.type == "add")//对于增加操作
			{
				++vmNum;
				double bestFit = INT_MAX;//bestFit的最小剩余
				//clock_t tempTime1, tempTime2, tempTime3, tempTime4;
				//tempTime1 = clock();
				addOption addOptionOfThis;
				addOptionOfThis.id = op.id;
				addOptionOfThis.isDoubleNode = vmMap[op.model].isDoubleNode;
				addOptionOfThis.model = op.model;
				bool findOne = false;//代表找到了一个合适的服务器
				int targetServer;
				bool isA = true;
				//先遍历已有的服务器，判断是否满足需要
				//tempTime3 = clock();
				auto& vm = vmMap[op.model];
				for (int serverId = 0; serverId < allServers.size(); ++serverId)
				{
					++cnt;
					auto &target = allServers[serverId];
					double punish = 1;
					if (allServers[serverId].vmId.empty())
						punish = 1.4;
					if (vm.isDoubleNode == true)//双节点部署
					{
						int c = vm.cpuCores / 2, m = vm.memorySize / 2;
						if (target.A_cpu >= c && target.B_cpu >= c && target.A_Memory >= m && target.B_Memory >= m)//可行
						{
							double thisLeft = 3 * pow((target.A_cpu + target.B_cpu - c * 2), 2) + pow((target.A_Memory + target.B_Memory - m * 2), 2);
							if (thisLeft*punish < bestFit)//计算分配后的价值是否小于当前最小剩余
								findOne = true, targetServer = serverId, bestFit = thisLeft;
						}
					}
					else
					{
						int c = vm.cpuCores, m = vm.memorySize;
						if (target.A_cpu >= c && target.A_Memory >= m)//能装下
						{
							double thisLeft = 3 * pow((target.A_cpu - c), 2) + pow((target.A_Memory - m), 2);
							if (thisLeft*punish < bestFit)
								findOne = true, targetServer = serverId, isA = true, bestFit = thisLeft;
						}
						else if (target.B_cpu >= c && target.B_Memory >= m)
						{
							double thisLeft = 3 * pow((target.B_cpu - c), 2) + pow((target.B_Memory - m), 2);
							if (thisLeft*punish < bestFit)
								findOne = true, targetServer = serverId, isA = false, bestFit = thisLeft;
						}
					}
				}
				//tempTime4 = clock();
				//findTime += (double)(tempTime4 - tempTime3) / CLOCKS_PER_SEC;
				if (findOne)//使用已有服务器，对服务器信息进行更新
				{
					allServers[targetServer].vmId.insert(op.id);
					allServers[targetServer].inUse = true;
					addOptionOfThis.serverID = targetServer;
					if (vm.isDoubleNode == true)//双节点部署
					{
						int c = vm.cpuCores / 2, m = vm.memorySize / 2;
						allServers[targetServer].A_cpu -= c;
						allServers[targetServer].B_cpu -= c;
						allServers[targetServer].A_Memory -= m;
						allServers[targetServer].B_Memory -= m;
					}
					else if (isA)
					{
						addOptionOfThis.isA = true;
						int c = vm.cpuCores, m = vm.memorySize;
						allServers[targetServer].A_cpu -= c;
						allServers[targetServer].A_Memory -= m;
					}
					else
					{
						addOptionOfThis.isA = false;
						int c = vm.cpuCores, m = vm.memorySize;
						allServers[targetServer].B_cpu -= c;
						allServers[targetServer].B_Memory -= m;
					}
				}
				else//如果已有服务器中找不到，就要购买一台
				{
					//tempTime3 = clock();
					string purchaseType;
					int c = vm.cpuCores, m = vm.memorySize;
					if (vm.isDoubleNode)
						c /= 2, m /= 2;

					if (day < 0.2 * TimesOfDay.size())
					{
						//选取能容纳的能耗最低的服务器进行购买
						for (int p = 0; p < serverList.size(); ++p)
							if (serverMap[serverList[p]].cpuCores / 2 >= c && serverMap[serverList[p]].memorySize / 2 >= m)
							{
								purchaseType = serverList[p];
								break;
							}
					}
					else
					{
						//尝试也使用best-fit算法找出购买的服务器
						double bestFitOfNew = INT_MAX;
						for (int p = 0; p < serverList.size(); ++p)
							if (serverMap[serverList[p]].cpuCores / 2 >= c && serverMap[serverList[p]].memorySize / 2 >= m)//可以容纳
								if (3 * pow(serverMap[serverList[p]].cpuCores / 2 - c, 2) + pow(serverMap[serverList[p]].memorySize / 2 - m, 2) < bestFitOfNew)
									purchaseType = serverList[p], bestFitOfNew = 3 * pow(serverMap[serverList[p]].cpuCores / 2 - c, 2) + pow(serverMap[serverList[p]].memorySize / 2 - m, 2);
					}

					////根据硬件成本+剩余天数*能耗成本对服务器成本进行评估，选取成本最低的服务器
					//double lowestCost = INT_MAX;
					//for (int p = 0; p < serverList.size(); ++p)
					//	if (serverMap[serverList[p]].cpuCores / 2 >= c && serverMap[serverList[p]].memorySize / 2 >= m)//可以容纳
					//		if (serverMap[serverList[p]].hardwareCost + (TimesOfDay.size() - day + 1) * serverMap[serverList[p]].energyCostPerDay < lowestCost)
					//			purchaseType = serverList[p], lowestCost = serverMap[serverList[p]].hardwareCost + (TimesOfDay.size() - day + 1) * serverMap[serverList[p]].energyCostPerDay;
					
					serverInfo newServer;
					newServer.model = purchaseType;
					if (vm.isDoubleNode)
					{
						newServer.A_cpu = serverMap[purchaseType].cpuCores / 2 - c;
						newServer.B_cpu = serverMap[purchaseType].cpuCores / 2 - c;
						newServer.A_Memory = serverMap[purchaseType].memorySize / 2 - m;
						newServer.B_Memory = serverMap[purchaseType].memorySize / 2 - m;
					}
					else
					{
						addOptionOfThis.isA = true;
						newServer.A_cpu = serverMap[purchaseType].cpuCores / 2 - c;
						newServer.A_Memory = serverMap[purchaseType].memorySize / 2 - m;
						newServer.B_cpu = serverMap[purchaseType].cpuCores / 2;
						newServer.B_Memory = serverMap[purchaseType].memorySize / 2;
					}
					newServer.energyCostPerDay = serverMap[purchaseType].energyCostPerDay;
					newServer.inUse = true;
					newServer.vmId.insert(op.id);
					if (purchase[purchaseType] == 0)//第一次购买这种服务器，对后续编号不产生影响
					{
						addOptionOfThis.serverID = allServers.size();//放在新服务器上
						++purchase[purchaseType];
						purchaseNum.push_back({ purchaseType,1 });
						allServers.push_back(newServer);
					}
					else//不是第一次购买，需要修改编号
					{
						int num =  allServers.size();
						for (int pos = purchaseNum.size() - 1; purchaseNum[pos].first != purchaseType; --pos)
							num -= purchaseNum[pos].second;
						addOptionOfThis.serverID = num;//放在新服务器上
						allServers.insert(allServers.begin() + num, newServer);//插入到服务器序列里
						for (int pos = num + 1; pos < allServers.size(); ++pos)//更改后面的服务器编号
							for (auto& idOfVm : allServers[pos].vmId)
								++addResult[idOfVm].serverID;
						++purchase[purchaseType];
						for (auto& p : purchaseNum)
							if (p.first == purchaseType)
								++p.second;
					}
					//tempTime4 = clock();
					//buyTime += (double)(tempTime4 - tempTime3) / CLOCKS_PER_SEC;
				}
				addResult[op.id] = addOptionOfThis;
				//addAnswer.push_back(addOptionOfThis);
				//tempTime2 = clock();
				//addTime += (double)(tempTime2 - tempTime1) / CLOCKS_PER_SEC;
			}
			else//对于删除操作，恢复原状
			{
				--vmNum;
				//clock_t tempTime1, tempTime2;
				//tempTime1 = clock();
				auto del = addResult[op.id];
				int c = vmMap[del.model].cpuCores, m = vmMap[del.model].memorySize;
				if (del.isDoubleNode)
					c /= 2, m /= 2;
				if (del.isDoubleNode)
				{
					allServers[del.serverID].A_cpu += c;
					allServers[del.serverID].B_cpu += c;
					allServers[del.serverID].A_Memory += m;
					allServers[del.serverID].B_Memory += m;
				}
				else if(del.isA)
				{
					allServers[del.serverID].A_cpu += c;
					allServers[del.serverID].A_Memory += m;
				}
				else
				{
					allServers[del.serverID].B_cpu += c;
					allServers[del.serverID].B_Memory += m;
				}
				allServers[del.serverID].vmId.erase(allServers[del.serverID].vmId.find(del.id));
				if (allServers[del.serverID].vmId.empty())
					allServers[del.serverID].inUse = false;
				//tempTime2 = clock();
				//delTime += (double)(tempTime2 - tempTime1) / CLOCKS_PER_SEC;
			}
		}
		//cout << beg << " " << index << endl;
		for (; beg < index; ++beg)
			if (allOperations[beg].type == "add")
				addAnswer.push_back(addResult[allOperations[beg].id]);
		printAnswer(purchaseNum, addAnswer,migrationAnswer);
		//return;
		//endTime = clock();
		//cout << cnt << " " << addTime << " " << delTime << " " << findTime << " " << buyTime << endl;
		//cout << "The run time of day " << day << " is:" << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
	}
}
int main()
{
	//freopen("in2.txt", "r", stdin);//测试用，读入文件
	//freopen("out2.txt", "w", stdout);//输出结果
	readData();
	//将服务器按能耗大小排序，小的在前
	sort(serverList.begin(), serverList.end(), [](auto& s1, auto& s2) {return serverMap[s1].energyCostPerDay < serverMap[s2].energyCostPerDay; });
	solve();
	return 0;
}