一键难忘520

这个屌丝很懒，什么也没留下！

热门标签

2021华为软件精英挑战赛总结分享_为什么软件挑战赛重点在调参

作者：一键难忘520 | 2024-08-02 16:21:11

踩

为什么软件挑战赛重点在调参

2021华为软件精英挑战赛总结分享

随着大赛的结束，自己的2021软挑也落下了帷幕，很幸运在自己学业生涯的最后几个月能够再参加一次华为软挑，虽然成绩不是特别好，但已经满足了。这是自己第二次参加华为的比赛，也是最后一次参加了，很感谢主办方华为，也是因为有了去年的比赛，才很幸运地在秋招能够拿到一些offer，在此，再次感谢华为公司，希望华为以后越来越好。

比赛成绩

队伍是成渝赛区，队伍名称：哑巴湖大水怪，成绩初赛：成渝第1，复赛：成渝第3，决赛拉跨，16强。
在这里插入图片描述

赛题介绍

赛题本质就是一个装箱问题和资源调度问题，比赛链接如下：2021华为软件精英挑战赛。

初赛方案

初赛赛题会提前一次性给出所有天的请求信息，所以很多队伍会利用这一上帝视角来进行服务器的选型以及部署，但自己实在是能力有限，不知道该如何利用好这一有效信息，因此也就没有利用这一信息，只是简单地对当前天的请求进行处理。

初赛赛题大家的优化点主要集中在三个部分：服务器选型、虚拟机部署和迁移。

1. 服务器选型

服务器选型应该大部分队伍的方案都差不多，我们的方案也是最简单的，在练习赛的时候使用的就是按照服务器售价排序，选择第一个能容纳下当前请求的服务器，也就是选择能容纳下当前虚拟机的最便宜的服务器。后面在正式赛的时候换成了按照服务器的日常能耗来排序成绩会更好。

2. 虚拟机部署

虚拟机部署这里应该很多队伍除了评价函数不一样之外，其他策略应该都是一样的，大家应该选择的都是best fit，但是重点就在评价函数这，有些评价函数太复杂，会使得计算时间上升。

我们队伍选择部署的策略是，遍历已有的服务器，找到使当前服务器某个节点剩余空间（CPU+内存）最小的服务器，也就是说评价函数就是当前这个服务器上两个节点剩余空间的min值，也就是说我的部署方案是尽量让服务器上的某个节点剩余空间最小，这个时候不再是以服务器为单位来评价了，而是以服务器上的节点维单位来评价。在找的过程同时还会记录虚拟机的部署位置，因为对于单节点部署的虚拟机，当我们在找最佳位置的时候，实际上是找服务器上哪个节点最适合，因此在找的同时记录位置，然后直接按照这个位置来部署。

如果找不到能放下的服务器，就按照上面的选型策略来购买新服务器。

3. 迁移

迁移这一块估计大家也都差不多，基本都是按照负载率来对服务器进行排序，然后尽量把低负载服务器上的虚拟机往高负载服务器上迁移，尽量空出更多的空服务器。但是，我们的方案有所不同。在练习赛的时候，我们尝试过按负载来排序，然后将低负载往高负载迁，后面发现迁移效果不佳。然后换了一个新思路，我们将服务器按照上面存放的虚拟机个数来排序，然后将个数为1，2，4的服务器上的虚拟机删除再重新部署。注意，我这里的迁移不一定非得是低负载到高负载，而是将这些被选中的虚拟机进行重新部署，重新寻找它最佳的位置，评价函数依然和虚拟机部署的一样，这也有可能找到的位置就是原位置，那就不进行迁移（我称之为无效迁移）。

然后师弟为了减少程序运行时间，只迁移每个服务器上的第1个虚拟机，我们发现效果更好，成本更低。因此我们又将迁移方案换成对服务器按照虚拟机个数排序，然后选取每个服务器上的第1个虚拟机进行迁移，这让我们在练习赛的时候的成绩已经能够进步到成渝第2。

在正赛的时候，我们发现按照负载率排序后，然后再选取第1个虚拟机进行迁移，成本会更低，因此在正赛我们又换成了按照负载率排序。

当然，这只是粗略的方案，迁移里面还会有很多细节，比如在寻找最佳位置的时候如果找到空服务器了，那就不进行迁移；比如如果待迁移的虚拟机是当天删除的，可以选择不迁移；前一天的删除请求比较少的时候要不要迁移，因为没必要每天都迁移；负载率的定义方式不同也会有影响。这些都是我们考虑的在正式赛调参的点。

4. 额外上分点

我们知道，装箱问题的方法除了Best Fit 和 First Fit，还有BFD和FFD，就是我们对虚拟机根据大小进行排序，先部署大的，再部署小的，这可以多利用一些有效空间，减少每个服务器的碎片。

但是这个赛题每天的请求还有要删除的虚拟机，有可能某个虚拟机当天创建当天删除，所以我们准备了两个思路。

1：将每一天所有的创建请求提前，也就是先处理所有的创建请求，再处理所有的删除请求。重点在于对所有的创建请求按照虚拟机占用空间进行排序，优先处理空间大的请求。这里有一个问题，就是因为前面的删除会被延后，那么它释放出的空间就没用到。但是这个是不可避免的，我们想的就是损失一部分删除空出来的空间，通过BFD的部署来弥补。

2：对每一天每两个删除请求之间的添加请求进行排序。这种方式就是会利用上删除的空间，但是有可能占用空间大的虚拟机请求比较靠后，这就没法提前部署它们。

这两个排序方式也是我们能够作为调参的点。

另外，我们在服务器选型和虚拟机部署那里还准备了一些其他的方案，反正就是各种试。

1：在服务器选型时，之前是选择最便宜的能容纳下当前虚拟机的服务器，那么我们在判断是否能容纳时，在虚拟机cpu和内存上乘一个系数，比如当前服务器是_server，虚拟机是_VMware，双节点部署，之前判断能否装下是 _server的每个节点的 cpu 和内存是否大于_VMware 的 cpu/2 和内存/2 ，这里我们会在_VMware的这里乘一个系数，比如是1.2，那就是 1.2cpu/2 和 1.2内存/2 。

2：在虚拟机部署时，考虑先在已有服务器上找最佳位置，找不到的话再在今天购买的服务器上找最佳位置。

3：在虚拟机部署时，先在已有的热机上找最佳位置，找不到的话再在冷机上找一个日耗最小的（因为一旦服务器开启就有日耗，那么优先找一个日耗最低的，尽量减少每天的日耗）。

4：多线程，因为线上提供的运行环境是2核的，所以可以开两个线程，使用两套不同的方案，相当于多一倍的提交机会。

复赛方案

复赛在初赛的基础上几乎没变化，就是没法提前知道所有的请求，只会给你提前K的请求，当你读完前K天的请求后，需要输出第一天的结果才能继续读取第K+1天的请求，这就涉及到交互。程序的改动很小，基本就是改一下输入输出就好了。且因为交互的原因排除了使用双线程跑两套方案的策略了。另外复赛还有一个改动就是增加了每天允许迁移的虚拟机的次数，这样大家有更多的迁移机会，同时也会让程序的运行时间增加，因此在复赛练习赛的时候优化代码运行时间也是很重要的一部分。

复赛的方案我们基本只改变了一下几个地方：

1. 服务器选型

之前初赛购买新服务器时是按照售价或者能耗从小到大排序来选择服务器的，在复赛练习赛的时候发现一个数据集适合按售价排序，一个数据集适合按能耗排序。在某个小学弟的指导下，尝试了一下在前期按照能耗排序，到后期按照售价排序。这么做的原因在于前期服务器生命周期长，能耗占比比较重，而到了后期服务器存活时间短，售价占比较重。改动之后，这个地方是一个非常大的上分点。我的区分前期后期的策略就是给一个时间的百分比，在练习赛的时候是前25%的天按照能耗，后75%的天按照售价；在正式赛的时候，这里是进步最大的参数，改为了前50%天按照能耗，后50%天按照售价。

2. 虚拟机部署

虚拟机部署这的改动不大，就是改动了一小部分的评价函数，之前初赛对于部署这一块的评价函数，是选择每个服务器上两个节点剩余空间的min值，然后再取所有服务器的min值进行部署，所以是两个min。在复赛时，我们对此处做了一定的更改，对于双节点部署的虚拟机，依然是选择两个min的方案。但是对于单节点部署，我们选择的是每个服务器上两个节点剩余空间的max值，然后再取所有服务器的min值进行部署，这么做的依据是在单节点部署时尽量使服务器的A、B节点比较均衡，所以会优先部署在剩余空间大的节点上。

另外，在练习赛的时候，我们在部署的时候选择 first fit 会比 best fit 更好，但在正式赛的时候，还是 best fit 更好。

3. 迁移

复赛的迁移基本策略与初赛基本一致，因为增加了每天允许的迁移次数，因此很多队伍成绩提升的很快，而且他们能在很短的时间内把迁移次数拉满，而当时我们的方案因为选择的是 best fit，因而会存在很多无效迁移，因而时间很长，同时没有办法把迁移次数拉满。

另外，我们的方案是选择每个服务器上的第一个虚拟机进行迁移，这个地方在复赛依然是十分有效的，只是这使得我们的迁移次数剩余太多，为了拉升迁移次数，我们多增加几次迁移轮次，就是添加一个while循环的问题。

迁移这里很费时间，因为每次迁移都要遍历所有的服务器来找最佳位置，因而为了减少时间，剪枝是必不可少的。主要使用了两个方面的剪枝。

设置一个负载率阈值，一旦某个服务器的负载率达到了这个阈值，就不对该服务器上的虚拟机进行迁移，另外为了减少迁移时间，会设置一个动态阈值，随着迁移轮次的增加，这个阈值会减少，这样约到后面能迁移的虚拟机就越少。比如，第一轮阈值设为0.99，以后每增加一轮，负载率就减少0.005。
对于迁移不动的某类虚拟机，做一个标记，下次迁移如果还是该类虚拟机，就直接跳过。比如在某一次迁移中，对于某类虚拟机，如果找了一遍发现还是只能在原来的位置，那么在下次遇到这种虚拟机的时候就直接continue，不执行查找的步骤，这在一定程度上能减少很多时间。

整体的迁移方案就是这样，需要调整的就是通过设置负载率阈值、前一轮次来进行调参。

4. 最大上分点

整个复赛，因为我们的方案基本没咋变，所以在前期的时候成绩一直不理想，而且要调的参数很多，很多参数都没法同时适应两个数据集。

在练习赛的最后两天，发现了一个上分点，直接把我的方案里的很多参数给去掉了。这个最大的上分点直接让我的练习赛成绩进步到了1740左右。这个上分点就是服务器合并。

具体的说就是对于处理某一天的请求，我会把服务器分为以前已有的服务器，和当天购买的服务器，当我处理完当天
的请求后，会对当天购买的服务器做一个合并的处理，思路也很简单。就是遍历这些服务器，如果相邻的两个服务器
上的虚拟机能够被某个更大的服务器容纳，且这个更大的服务器的售价和能耗都小于之前这两个相邻的服务器的售价
之和和能耗之和，那就用这个更大的服务器来代替之前的两个服务器。
1
2
3
4

复赛正式赛需求变更点

复赛正式赛需求变更点就是允许某一天的迁移次数能突破3%限制，可以达到100%，现场分析后可知因为只有某一天才能有这个机会，所以对成绩的改动并不大，基本只有几十万的提升。我们选择的策略就是如果某一天的删除次数大于500，那么我们就在下一天使用该策略。

决赛方案

决赛的赛题变动比较大，增加了报价部分，多了与对手博弈的部分。具体的赛题更新部分我会发在github上，这里就不详细论述了。主要说一下我们的方案。

因为决赛多了博弈的部分后我不是很喜欢这种模式，又恰逢当时学校有事，感觉自己也没实力拿前八，基本就属于半放弃了，匆匆写了两个版本后基本就不管了。

版本一：动态打折。为了抢到虚拟机单子，起始设置一个较低的折扣，然后通过统计自己前一天的获单量来决定增大还是减小自己的折扣。这个方案基本是大家都知道的方案，所以被暴打。

版本二：预估自己的最低成本进行报价。会增加一个预部署的步骤，假装自己能够拿到所有的虚拟机请求，进行部署，根据每个虚拟机占用的服务器资源比，对虚拟机进行最低定价。版本二基本在前期就是成本价，因此在后期因为亏得比较多，只能按照请求给得全价来报价。这个方案练习赛也只能10几名。最后正式赛使用的就是版本二。

决赛正式赛需求变更点

在决赛正式赛的时候，需求变更点特别大，导致直接颠覆练习赛的排名，需求变更是每一天我们都可以对3个请求进行指定，这3个请求一旦指定后，就算对手的报价比你低，你也可以按照你的报价拿到。但是如果对手也指定了这个请求，那么谁出价低谁拿到。

当时一想，每天能拿到3个，大家应该都会拿存活时间较长的虚拟机，1000天就可以拿3000个，那这个上分点影响实在是太大了，一旦对手抢不过你，那基本就是吊打对面。

所以我们很快实现了这个需求点，对自己要指定的3个请求进行报价，为了避免对手也指定这3个，且价格比我们低，所以我们对于指定的请求进行了一个折扣，为了一定的随机性，我们指定了3个折扣，对于某个请求根据随机值来选择使用哪个折扣，这在练习赛的时候使得我们一直维持在前排。但这同时也暴露了我们得策略，因为只有3种折扣，对手很快就能计算出来。这也是我们很后悔的一点，应该设置一个区间打折的，只有三个，太容易被看出来了。

因为决赛是PK制的，在苟活了两轮之后被干下去了，没能进入八强，不过本身因为自己决赛并没有肝，是以一个挑战者的身份来的，所以并没有很失落。

整个软挑比赛下来就是这样，成绩中规中矩，但好在进了决赛，弥补了自己去年没能进入决赛的遗憾，具体的代码我会放在下面，因为自己代码写的太烂了，全程都只有一个文件，大家看看思路就行。

另外去年的比赛博客写了一半，拖了一年还没写完，准备趁此机会，一并写了。

本来还想取官网看看决赛的对战日志的，发现已经找不到入口了，算了算了。

初赛正式赛代码

#include <bits/stdc++.h>
using namespace std;

#define TEST
#define FILE
string filePath;

int number = 0;

// 服务器对应信息表
// 服务器模板
struct serverTemplate {
    serverTemplate(){}
    serverTemplate(string type, int core, int mem, int price, int cost){
        this->type = type;
        this->core = core;
        this->mem = mem;
        this->price = price;
        this->cost = cost;
    }
    string type;
    int core;
    int mem;
    int price;
    int cost;
};
// 服务器
struct server {
    server(){}
    server(serverTemplate st, int id, int coreA, int coreB, int memA, int memB){
        this->st = st;
        this->coreA = coreA;
        this->coreB = coreB;
        this->memA = memA;
        this->memB = memB;
        this->id = id;
    }
    serverTemplate st;
    int id;
    int coreA;
    int coreB;
    int memA;
    int memB;
};
// 虚拟机
struct VMware {
    VMware(){}
    VMware(int core, int mem, int binode) {
        this->core = core;
        this->mem = mem;
        this->binode = binode;
    }
    int core;       // 核心数
    int mem;        // 内存
    int binode;     // 是否双节点部署
};
// 部署信息
struct inform {
    inform(){}
    inform(string _st, int _id, string _ed) {
        st = _st;
        id = _id;
        ed = _ed;
    }
    string st;
    int id;
    string ed;
};

/* ------------------------------服务器部署所需信息------------------------------ */
// 天数, 服务器类型数, 虚拟机类型数
int days, serverKind, VMwareKind;
int serverID = 0, VMwareNum = 0;
// 服务器型号表
unordered_map<string, serverTemplate> serverTable;
// 将服务器按照成本排序
vector<serverTemplate> orderedServer;
// 虚拟机型号表
unordered_map<string, VMware> VMwareTable;
// 已购买服务器集群
vector<server> serverCluster;
// 虚拟机ID对照表
unordered_map<int, VMware> VMwareCluster;
// 每天的请求信息
vector<vector<pair<string, int>>> quest;
// 记录虚拟机运行在哪个服务器的哪个节点上
unordered_map<int, pair<int, int>> VMwareOnServer;
// 当前开机服务器, 表示上面部署了多少台虚拟机
vector<list<int>> serverRun;

// 每天添加的服务器对应的ID以及排序后的映射
vector<vector<pair<string, int>>> befSer2ID;
unordered_map<int, string> aftMapping;
// 记录每一天增加的每种服务器的数量
vector<vector<pair<string, int>>> serDayNum;
// 记录每天的虚拟机部署情况
vector<vector<inform>> dayResult;
// 记录每天的虚拟机迁移情况
vector<vector<inform>> migrateResult;
// 记录虚拟机删除的日期
unordered_map<int, int> deleteDay;
// 记录虚拟机添加的日期
unordered_map<int, int> addDay;
// 每天的添加删除次数，0为添加次数、1为删除次数
vector<vector<int>> addDelTimes;
// 输出字符串
string result;
// 待迁移的虚拟机ID
vector<int> vmwareVec;
// 待迁移的虚拟机信息，键是虚拟机ID，值是以前位于的服务器的ID和节点
unordered_map<int, pair<int, int>> vmwareOnVec;
// 记录当天创建当天删除的部署在新服务器上的虚拟机
vector<int> vmAddDelSameDay;
// 成本
long long purchaseCost, dailyCost, totalCost;
int serNumDay;

// 文件输入
void readInfo() {
#ifdef FILE
    std::freopen(filePath.c_str(),"rb",stdin);
#endif
    /* 读取并保存服务器信息--------------------------- */
    cin >> serverKind;
    string typeStr, coreStr, memStr, priceStr, costStr;
    for(int i = 0; i < serverKind; i++) {
        cin >> typeStr >> coreStr >> memStr >> priceStr >> costStr;
        string _typeStr;
        _typeStr = typeStr.substr(1, typeStr.size()-2);

        int _core = 0, _mem = 0, _price = 0, _cost = 0;
        _core = stoi(coreStr.substr(0, coreStr.size()-1));
        _mem = stoi(memStr.substr(0, memStr.size()-1));
        _price = stoi(priceStr.substr(0, priceStr.size()-1));
        _cost = stoi(costStr.substr(0, costStr.size()-1));

        serverTable[_typeStr] = serverTemplate(_typeStr, _core, _mem, _price, _cost);
		orderedServer.push_back(serverTable[_typeStr]);
    }
    /* 读取并保存虚拟机信息--------------------------- */
    cin >> VMwareKind;
    string VMtypeStr, VMcoreStr, VMmemStr, VMbinode;
    for(int i = 0; i < VMwareKind; i++) {
        cin >> VMtypeStr >> VMcoreStr >> VMmemStr >> VMbinode;
        string _VMtypeStr;
        _VMtypeStr = VMtypeStr.substr(1, VMtypeStr.size()-2);

        int _VMcore = 0, _VMmem = 0, _VMbinode = 0;
        _VMcore = stoi(VMcoreStr.substr(0, VMcoreStr.size()-1));
        _VMmem = stoi(VMmemStr.substr(0, VMmemStr.size()-1));
        if(VMbinode[0] == '1') {
            _VMbinode = 1;
        } else {
            _VMbinode = 0;
        }
        VMwareTable[_VMtypeStr] = VMware(_VMcore, _VMmem, _VMbinode);
    }
    /* 读取并保存用户请求信息--------------------------- */
    cin >> days;
    befSer2ID.resize(days);
    serDayNum.resize(days);
    dayResult.resize(days);
    migrateResult.resize(days);
	addDelTimes.resize(days, vector<int>(2, 0));
    // 请求类型， 虚拟机型号，虚拟机ID
    string opera, VMtype, VMID;
    for(int t = 0; t < days; t++) {
        //记录当天的请求
        vector<pair<string, int>> questTemp;
        int n;  // 每天n个请求
        cin >> n;
        for(int i = 0; i < n; i++) {
            // 先读取请求类型
            cin >> opera;
            // 格式化后的请求类型， 虚拟机型号，虚拟机ID
            string _opera, _VMtype, _VMID;
            // 如果是添加请求
            if(opera[1] == 'a') {
                cin >> VMtype >> VMID;
                _opera = opera.substr(1, opera.size() - 2);
                _VMtype = VMtype.substr(0, VMtype.size() - 1);
                _VMID = VMID.substr(0, VMID.size() - 1);
                VMwareCluster[stoi(_VMID)] = VMwareTable[_VMtype];
				addDay[stoi(_VMID)] = t;
				addDelTimes[t][0]++;
            }
            // 如果是删除请求，表明删除已有虚拟机
            else {
                cin >> VMID;
                _opera = opera.substr(1, opera.size() - 2);
                _VMID = VMID.substr(0, VMID.size() - 1);
				deleteDay[stoi(_VMID)] = t;
				addDelTimes[t][1]++;
            }
            // 记录下此时的请求类型和ID
            questTemp.push_back(make_pair(_opera, stoi(_VMID)));
        }
        // 将当天请求保存下来
        quest.push_back(questTemp);
    }
}

// serverTemplate按照成本比较
bool cmp1(serverTemplate &s1, serverTemplate &s2) {
    return s1.cost < s2.cost;// 这里到了后面换成price也只是影响10w级别的成绩

}

// 对服务器排序
void sortServer() {
    sort(orderedServer.begin(), orderedServer.end(), cmp1);
}

// 部署: 将ID为VMwareIdx的虚拟机部署在_server的deployNode节点上
void chooseServer(server &_server, int VMwareIdx, int deployNode) {
    int serverIdx = _server.id;
    auto &_VMware = VMwareCluster[VMwareIdx];
    // 如果是双节点部署
    if(deployNode == 2) {
        _server.coreA -= _VMware.core/2;
        _server.coreB -= _VMware.core/2;
        _server.memA -= _VMware.mem/2;
        _server.memB -= _VMware.mem/2;
        VMwareOnServer[VMwareIdx] = make_pair(serverIdx, 2);
    }
    // 如果是A节点部署
    else if(deployNode == 0) {
        _server.coreA -= _VMware.core;
        _server.memA -= _VMware.mem;
        VMwareOnServer[VMwareIdx] = make_pair(serverIdx, 0);

    }
    // 如果为B节点部署
    else {
        _server.coreB -= _VMware.core;
        _server.memB -= _VMware.mem;
        VMwareOnServer[VMwareIdx] = make_pair(serverIdx, 1);
    }
}

// 判断新服务器能否部署，这个地方上分最多，接近1000w了
int haveFreeSpace(server &serverInfo, VMware &vm) {
    if (vm.binode == 1) {
        if (serverInfo.coreA >= 10*vm.core/9 && serverInfo.coreB >= 10*vm.core/9 && serverInfo.memA >= 10*vm.mem/9 && serverInfo.memB >= 10*vm.mem/9) {
            return 2;
        }
    } else {
        if (serverInfo.coreA >= vm.core && serverInfo.memA >= vm.mem) {
			// 这里保证要选择的服务器和虚拟机的cpu和mem的大小关系一致
			if((_server.st.core-_server.st.mem)*(vm.core-vm.mem) >= 0) return 0; 
        }

        if (serverInfo.coreB >= vm.core && serverInfo.memB >= vm.mem) {
			if((_server.st.core-_server.st.mem)*(vm.core-vm.mem) >= 0) return 1;
        }
    }
    return -1;
}

/* 部署策略是找部署后剩余节点最小的那个服务器的节点 */

// 对vmId虚拟机进行部署 方案0，找服务器最佳的
void createVMware(int VMID, int day) {
    // 获取该虚拟机信息
    VMware &_VMware = VMwareCluster[VMID];
	int idx = -1, deployNode = -1;
	int minScore = INT_MAX;
	for(int i = 0; i < serverID; i++) {
		auto &_server = serverCluster[i];
		int score = INT_MAX;
		int node = -1;
		if(_VMware.binode == 1) {
			if(_server.coreA >= _VMware.core/2 && _server.memA >= _VMware.mem/2 && _server.coreB >= _VMware.core/2 && _server.memB >= _VMware.mem/2) {
				score = min(_server.coreA+_server.memA, _server.coreB+_server.memB) - _VMware.core/2 - _VMware.mem/2;
				node = 2;
			}
		}
		else {
			if(_server.coreA >= _VMware.core && _server.memA >= _VMware.mem) {
				int tmp = _server.coreA-_VMware.core+_server.memA-_VMware.mem;
				if(tmp < score) {
					score = tmp;
					node = 0;
				}
			}
			if(_server.coreB >= _VMware.core && _server.memB >= _VMware.mem) {
				int tmp = _server.coreB-_VMware.core+_server.memB-_VMware.mem;
				// double tmp = 1.0*(_server.st.core/2-_server.coreB+_VMware.core+_server.st.mem/2-_server.memB+_VMware.mem)/(_server.st.core/2+_server.st.mem/2);
				if(tmp < score) {
					score = tmp;
					node = 1;
				}
			}
		}

		if(node != -1 && score < minScore) {
			minScore = score;
			idx = i;
			deployNode = node;
		}
	}
	if(idx != -1) {
		auto &_s = serverCluster[idx];
		chooseServer(_s, VMID, deployNode);
		serverRun[_s.id].push_back(VMID);
		assert(_s.coreA >= 0 && _s.coreB >= 0 && _s.memA >= 0 && _s.memB >= 0);
		assert(_s.coreA <= _s.st.core/2 && _s.coreB <= _s.st.core/2 && _s.memA <= _s.st.mem/2 && _s.memB <= _s.st.mem/2);
		return;
	}
    // 如果已有服务器部署失败
    for(auto &st : orderedServer) {
        auto s = server(st, -1, st.core/2, st.core/2, st.mem/2, st.mem/2);
        // 如果服务器合适，选择该服务器
		int node = haveFreeSpace(s, _VMware);
        if(node != -1) {
            befSer2ID[day].push_back(make_pair(s.st.type, serverID));
            s.id = serverID;
			serverID++;
            serverCluster.push_back(s);
            purchaseCost += s.st.price;
            // 重新部署
            chooseServer(serverCluster[serverID-1], VMID, node);
            serverRun.push_back(list<int>{VMID});
			assert(serverCluster[serverID-1].coreA >= 0 && serverCluster[serverID-1].coreB >= 0 && serverCluster[serverID-1].memA >= 0 && serverCluster[serverID-1].memB >= 0);
			break;
        }
    }
}

// 对vmId虚拟机进行部署 方案1，先在非空服务器购买，再在空服务器选energy最小的
void createVMware1(int VMID, int day) {
    // 获取该虚拟机信息
    VMware &_VMware = VMwareCluster[VMID];
	int idx = -1, deployNode = -1;
	int minScore = INT_MAX;
	// 先在非空的服务器上找
	for(int i = 0; i < serverID; i++) {
		auto &_server = serverCluster[i];
		if(serverRun[_server.id].empty()) continue;
		int score = INT_MAX, node = -1;
		if(_VMware.binode == 1) {
			if(_server.coreA >= _VMware.core/2 && _server.memA >= _VMware.mem/2 && _server.coreB >= _VMware.core/2 && _server.memB >= _VMware.mem/2) {
				score = min(_server.coreA+_server.memA, _server.coreB+_server.memB) - _VMware.core/2 - _VMware.mem/2;
				node = 2;
			}
		}
		else {
			if(_server.coreA >= _VMware.core && _server.memA >= _VMware.mem) {
				int tmp = _server.coreA-_VMware.core+_server.memA-_VMware.mem;
				if(tmp < score) {
					score = tmp;
					node = 0;
				}
			}
			if(_server.coreB >= _VMware.core && _server.memB >= _VMware.mem) {
				int tmp = _server.coreB-_VMware.core+_server.memB-_VMware.mem;
				if(tmp < score) {
					score = tmp;
					node = 1;
				}
			}
		}

		if(node != -1 && score < minScore) {
			minScore = score;
			idx = i;
			deployNode = node;
		}
	}
	if(idx != -1) {
		auto &_s = serverCluster[idx];
		chooseServer(_s, VMID, deployNode);
		serverRun[_s.id].push_back(VMID);
		assert(_s.coreA >= 0 && _s.coreB >= 0 && _s.memA >= 0 && _s.memB >= 0);
		assert(_s.coreA <= _s.st.core/2 && _s.coreB <= _s.st.core/2 && _s.memA <= _s.st.mem/2 && _s.memB <= _s.st.mem/2);
		return;
	}
	// 再在空服务器上找
	for(int i = 0; i < serverID; i++) {
		auto &_server = serverCluster[i];
		if(!serverRun[_server.id].empty()) continue;
		int score = INT_MAX, node = -1;
		
		node = haveFreeSpace(_server, _VMware);
		if(node == -1) continue;
		score = _server.st.cost;
		if(score < minScore) {
			minScore = score;
			idx = i;
			deployNode = node;
		}
	}
	if(idx != -1) {
		auto &_s = serverCluster[idx];
		chooseServer(_s, VMID, deployNode);
		serverRun[_s.id].push_back(VMID);
		assert(_s.coreA >= 0 && _s.coreB >= 0 && _s.memA >= 0 && _s.memB >= 0);
		assert(_s.coreA <= _s.st.core/2 && _s.coreB <= _s.st.core/2 && _s.memA <= _s.st.mem/2 && _s.memB <= _s.st.mem/2);
		return;
	}	
    // 如果已有服务器部署失败
    for(auto &st : orderedServer) {
        auto s = server(st, -1, st.core/2, st.core/2, st.mem/2, st.mem/2);
        // 如果服务器合适，选择该服务器
		int node = haveFreeSpace(s, _VMware);
        if(node != -1) {
            befSer2ID[day].push_back(make_pair(s.st.type, serverID));
            s.id = serverID;
			serverID++;
            serverCluster.push_back(s);
            purchaseCost += s.st.price;
            // 重新部署
            chooseServer(serverCluster[serverID-1], VMID, node);
            serverRun.push_back(list<int>{VMID});
			assert(serverCluster[serverID-1].coreA >= 0 && serverCluster[serverID-1].coreB >= 0 && serverCluster[serverID-1].memA >= 0 && serverCluster[serverID-1].memB >= 0);
			break;
        }
    }
}

// 对vmId虚拟机进行部署 方案2，将服务器分为之前购买的，和当天要购买的，现在之前购买的服务器里找，找不到，再在当天购买的服务器里找
void createVMware2(int VMID, int day) {
    // 获取该虚拟机信息
    VMware &_VMware = VMwareCluster[VMID];
	int idx = -1, deployNode = -1;
	int minScore = INT_MAX;
	for(int i = 0; i < serNumDay; i++) {
		auto &_server = serverCluster[i];
		int score = INT_MAX, node = -1;
		if(_VMware.binode == 1) {
			if(_server.coreA >= _VMware.core/2 && _server.memA >= _VMware.mem/2 && _server.coreB >= _VMware.core/2 && _server.memB >= _VMware.mem/2) {
				score = min(_server.coreA+_server.memA, _server.coreB+_server.memB) - _VMware.core/2 - _VMware.mem/2;
				node = 2;
			}
		}
		else {
			if(_server.coreA >= _VMware.core && _server.memA >= _VMware.mem) {
				int tmp = _server.coreA-_VMware.core+_server.memA-_VMware.mem;
				if(tmp < score) {
					score = tmp;
					node = 0;
				}
			}
			if(_server.coreB >= _VMware.core && _server.memB >= _VMware.mem) {
				int tmp = _server.coreB-_VMware.core+_server.memB-_VMware.mem;
				if(tmp < score) {
					score = tmp;
					node = 1;
				}
			}
		}

		if(node != -1 && score < minScore) {
			minScore = score;
			idx = i;
			deployNode = node;
		}
	}
	if(idx != -1) {
		auto &_s = serverCluster[idx];
		chooseServer(_s, VMID, deployNode);
		serverRun[_s.id].push_back(VMID);
		assert(_s.coreA >= 0 && _s.coreB >= 0 && _s.memA >= 0 && _s.memB >= 0);
		assert(_s.coreA <= _s.st.core/2 && _s.coreB <= _s.st.core/2 && _s.memA <= _s.st.mem/2 && _s.memB <= _s.st.mem/2);
		return;
	}
	// 再在当天新加的服务器上找
	for(int i = serNumDay; i < serverID; i++) {
		auto &_server = serverCluster[i];
		int score = INT_MAX, node = -1;
		if(_VMware.binode == 1) {
			if(_server.coreA >= _VMware.core/2 && _server.memA >= _VMware.mem/2 && _server.coreB >= _VMware.core/2 && _server.memB >= _VMware.mem/2) {
				score = min(_server.coreA+_server.memA, _server.coreB+_server.memB) - _VMware.core/2 - _VMware.mem/2;
				node = 2;
			}
		}
		else {
			if(_server.coreA >= _VMware.core && _server.memA >= _VMware.mem) {
				int tmp = _server.coreA-_VMware.core+_server.memA-_VMware.mem;
				if(tmp < score) {
					score = tmp;
					node = 0;
				}
			}
			if(_server.coreB >= _VMware.core && _server.memB >= _VMware.mem) {
				int tmp = _server.coreB-_VMware.core+_server.memB-_VMware.mem;
				if(tmp < score) {
					score = tmp;
					node = 1;
				}
			}
		}

		if(node != -1 && score < minScore) {
			minScore = score;
			idx = i;
			deployNode = node;
		}

	}
	// 如果找到了
	if(idx != -1) {
		// 在已有服务器上部署
		auto &_s = serverCluster[idx];
		chooseServer(_s, VMID, deployNode);
		serverRun[_s.id].push_back(VMID);
		assert(_s.coreA >= 0 && _s.coreB >= 0 && _s.memA >= 0 && _s.memB >= 0);
		assert(_s.coreA <= _s.st.core/2 && _s.coreB <= _s.st.core/2 && _s.memA <= _s.st.mem/2 && _s.memB <= _s.st.mem/2);
		return;
	}
	// 找不到再找能装下该虚拟机的
	for(int i = 0; i < orderedServer.size(); i++) {
		auto &st = orderedServer[i];
        auto s = server(st, -1, st.core/2, st.core/2, st.mem/2, st.mem/2);
        // 如果服务器合适，选择该服务器
		int node = haveFreeSpace(s, _VMware);
        if(node != -1) {
            befSer2ID[day].push_back(make_pair(s.st.type, serverID));
            s.id = serverID;
			serverID++;
            serverCluster.push_back(s);
            purchaseCost += s.st.price;
            // 重新部署
            chooseServer(serverCluster[serverID-1], VMID, node);
            serverRun.push_back(list<int>{VMID});
			assert(serverCluster[serverID-1].coreA >= 0 && serverCluster[serverID-1].coreB >= 0 && serverCluster[serverID-1].memA >= 0 && serverCluster[serverID-1].memB >= 0);
			break;
        }
    }
}

// 删除请求
void delVMware(int VMID) {
    int serverIdx = VMwareOnServer[VMID].first;
    serverRun[serverIdx].remove(VMID);
    // 释放对应的server上的资源占用情况
    auto &_server = serverCluster[serverIdx];

	if(VMwareOnServer[VMID].second == 2) {
        _server.coreA += VMwareCluster[VMID].core/2;
        _server.coreB += VMwareCluster[VMID].core/2;
        _server.memA += VMwareCluster[VMID].mem/2;
        _server.memB += VMwareCluster[VMID].mem/2;
    }
    else {
        if(VMwareOnServer[VMID].second == 0) {
            _server.coreA += VMwareCluster[VMID].core;
            _server.memA += VMwareCluster[VMID].mem;
        }
        else {
            _server.coreB += VMwareCluster[VMID].core;
            _server.memB += VMwareCluster[VMID].mem;
        }
    }

    VMwareOnServer.erase(VMID);
}

// 对请求排序
bool cmp4(pair<string, int> &p1, pair<string, int> &p2) {
	int vmid1 = p1.second;
	int vmid2 = p2.second;
	return VMwareCluster[vmid1].core+VMwareCluster[vmid1].mem > VMwareCluster[vmid2].core+VMwareCluster[vmid2].mem;
}

// 处理第day天的请求
void serverAllocation(int day) {
	vector<pair<string, int>> request;
	
	// 分add和del排序
	vector<pair<string, int>> request1;	
	vector<pair<string, int>> request2;	
	for(auto req : quest[day]) {
		if(req.first == "add") {
			request1.push_back(req);
		}
		else {
			request2.push_back(req);
		}
	}
	sort(request1.begin(), request1.end(), cmp4);
	for(auto &req : request1) request.push_back(req);
	for(auto &req : request2) request.push_back(req);
	
	// 每两个del之间的add排序
	// auto request = quest[day];
	// int i = 0, j = 0;
	// while(j < request.size()) {
		// if(request[j].first == request[i].first) {
			// j++;
		// } else {
			// if(request[i].first == "add" && j-i > 1) {
				// sort(request.begin()+i, request.begin()+j, cmp4);
			// }
			// i = j;
		// }
	// }
	// if(j == request.size() && j-i > 1 && request[i].first == "add") {
		// sort(request.begin()+i, request.end(), cmp4);
	// }
	

    // 处理请求信息
	for(int i = 0; i < request.size(); i++) {
		auto &req = request[i];
        // 如果是add
        if(req.first == "add") {
            int VMID = req.second;
            createVMware(VMID, day);
            VMwareNum++;
        }
        else {
            int VMID = req.second;
            delVMware(VMID);
            VMwareNum--;
        }
    }
	// 保存部署信息
	for(int i = 0; i < quest[day].size(); i++) {
		auto &req = quest[day][i];
        // 如果是add
        if(req.first == "add") {
            int VMID = req.second;
            if(VMwareOnServer[VMID].second == 0) dayResult[day].push_back(inform("(", VMwareOnServer[VMID].first, ", A)\n"));
			else if(VMwareOnServer[VMID].second == 1) dayResult[day].push_back(inform("(", VMwareOnServer[VMID].first, ", B)\n"));
			else dayResult[day].push_back(inform("(", VMwareOnServer[VMID].first, ")\n"));
        }
    }
}

// 负载率排序函数
bool cmp5(server &s1, server &s2) {
	// double radio1 = pow(1.0*(s1.st.core-s1.coreA-s1.coreB)/s1.st.core, 2)+pow(1.0*(s1.st.mem-s1.memA-s1.memB)/s1.st.mem, 2);
	// double radio2 = pow(1.0*(s2.st.core-s2.coreA-s2.coreB)/s2.st.core, 2)+pow(1.0*(s2.st.mem-s2.memA-s2.memB)/s2.st.mem, 2);
	// double radio1 = 1.0*(s1.st.core-s1.coreA-s1.coreB + s1.st.mem-s1.memA-s1.memB)/(s1.st.core + s1.st.mem);
	// double radio2 = 1.0*(s2.st.core-s2.coreA-s2.coreB + s2.st.mem-s2.memA-s1.memB)/(s2.st.core + s2.st.mem);
	double radio1 = 1.0*(s1.st.core-s1.coreA-s1.coreB)/s1.st.core + 1.0*(s1.st.mem-s1.memA-s1.memB)/s1.st.mem;
	double radio2 = 1.0*(s2.st.core-s2.coreA-s2.coreB)/s2.st.core + 1.0*(s2.st.mem-s2.memA-s2.memB)/s2.st.mem; // 这里我把负载率计算换成这个之后上了100多w
	return radio1 < radio2;
}

// 迁移策略：服务器按负载排序，然后取每个服务器上的第一个，最后直接删除重新部署
void migration(int day) {

	int times = VMwareNum/200;
	if(times == 0) return;

    vmwareVec.clear();
	vmwareOnVec.clear();
	auto tmp = serverCluster;
	sort(tmp.begin(), tmp.end(), cmp5);
	
	for(int i = 0; i < tmp.size(); i++) {
		int id = tmp[i].id;
		if(serverRun[id].size() == 0) continue;

		int n = 1;
		for(auto VMID : serverRun[id]) {
			// if(deleteDay[VMID] == day) continue;
			vmwareVec.push_back(VMID);
			vmwareOnVec[VMID] = VMwareOnServer[VMID];
			n--;
			if(n <= 0) break;
		}

    }
	
    for(int i = 0; i < vmwareVec.size() ; i++) {
        int VMID = vmwareVec[i];
		int serID = vmwareOnVec[VMID].first;

        // 先删除虚拟机
		delVMware(VMID);
		// 再重新部署
        VMware &_VMware = VMwareCluster[VMID];

        int idx = -1, deployNode = -1;
        int minScore = INT_MAX;
		double maxScore = DBL_MIN;
        for(int i = 0; i < serverID; i++) {
			
            auto &_server = serverCluster[i];
            int score = INT_MAX;
			int node = -1;
            if(_VMware.binode == 1) {
                if(_server.coreA >= _VMware.core/2 && _server.memA >= _VMware.mem/2 && _server.coreB >= _VMware.core/2 && _server.memB >= _VMware.mem/2) {
                    score = min(_server.coreA+_server.memA, _server.coreB+_server.memB) - _VMware.core/2 - _VMware.mem/2;
					node = 2;
                }
            }
            else {
                if(_server.coreA >= _VMware.core && _server.memA >= _VMware.mem) {
                    int tmp = _server.coreA-_VMware.core+_server.memA-_VMware.mem;
                    if(tmp < score) {
                        score = tmp;
                        node = 0;
                    }
                }
                if(_server.coreB >= _VMware.core && _server.memB >= _VMware.mem) {
                    int tmp = _server.coreB-_VMware.core+_server.memB-_VMware.mem;
                    if(tmp < score) {
                        score = tmp;
                        node = 1;
                    }
                }
            }

            if(node != -1 && score < minScore) {
                minScore = score;
                idx = i;
                deployNode = node;
            }
        }
        if(idx != -1) {
			// 如果迁到了空服务器上，就不迁
			if(idx != serID && serverRun[idx].size() == 0) {
				idx = vmwareOnVec[VMID].first;
				deployNode = vmwareOnVec[VMID].second;
			}
            auto &_s = serverCluster[idx];
            chooseServer(_s, VMID, deployNode);
            serverRun[_s.id].push_back(VMID);
            if(vmwareOnVec[VMID] != VMwareOnServer[VMID]) {
                if(deployNode == 0) {
                    migrateResult[day].push_back(inform("("+to_string(VMID)+", ", _s.id, ", A)\n"));
                } else if(deployNode == 1) {
                    migrateResult[day].push_back(inform("("+to_string(VMID)+", ", _s.id, ", B)\n"));
                } else {
                    migrateResult[day].push_back(inform("("+to_string(VMID)+", ", _s.id, ")\n"));
                }
                times--;
            } else {
				number++;
			}
			
        }
		if(times <= 0) break;

    }
}

// 日常损耗
void serverCost() {
    for(int i = 0; i < serverID; i++) {
        if(serverRun[i].size()) {
            dailyCost += serverCluster[i].st.cost;
        }
    }
}

// 按序处理请求
void processing() {
    for(int t = 0; t < days; t++) {
        #ifdef TEST
            // if(t%100 == 0) cout << "t = " << t << endl;
        #endif
        serNumDay = serverID;
		vmAddDelSameDay.clear();
        if(t != 0 && addDelTimes[t-1][1] != 0) migration(t); // 如果前一天没有删除操作就不迁移
		// if(t != 0) migration(t);
        serverAllocation(t);
        // 最后计算日常损耗
		serverCost();
    }
}
// 用于服务器ID映射
bool mycmp(pair<string, int> &a, pair<string, int> &b) {
    return a.first < b.first;
}

// 服务器ID映射
void mapping() {
    for(int i = 0 ; i < days; i++) {
        // 记录起始数字
		if(befSer2ID[i].empty()) continue;
        int st = befSer2ID[i][0].second;
        // 排序
        sort(befSer2ID[i].begin(), befSer2ID[i].end(), mycmp);
        // 映射
        for(int j = 0; j < befSer2ID[i].size(); j++) {
            auto &temp = befSer2ID[i][j];
            aftMapping[temp.second] = to_string(st);
            st++;
            // 按顺序统计出现次数，方便后面输出
            if(j == 0) {
                serDayNum[i].push_back(make_pair(befSer2ID[i][j].first, 1));
            } else {
                if(befSer2ID[i][j].first == serDayNum[i].back().first) {
                    serDayNum[i].back().second++;
                } else {
                    serDayNum[i].push_back(make_pair(befSer2ID[i][j].first, 1));
                }
            }
        }
    }
}

// 组合输出字符串
void splic() {
    for(int i = 0; i < days; i++) {
        // 先拼接购买信息
        int num = serDayNum[i].size();
        result += "(purchase, " + to_string(num) + ")\n";
        if(num != 0) {
            for(int j = 0; j < num; j++) {
                result += "(" + serDayNum[i][j].first + ", " + to_string(serDayNum[i][j].second) + ")\n";
            }
        }
        // 再拼接迁移信息
        if(migrateResult[i].size() == 0) result += "(migration, 0)\n";
        else {
			result += "(migration, " + to_string(migrateResult[i].size()) + ")\n";
            for(int j = 0; j < migrateResult[i].size(); j++) {
                auto &mig = migrateResult[i][j];
                result += mig.st;
                result += aftMapping[mig.id];
                result += mig.ed;
            }
        }
        // 再拼接部署信息
        for(int j = 0; j < dayResult[i].size(); j++) {
            auto &info = dayResult[i][j];
            result += info.st;
            result += aftMapping[info.id];
            result += info.ed;
        }
    }
}

int main(int argc, char* argv[]) {
	string s(argv[1]);
	filePath = "./data/training-" + s + ".txt";
    readInfo();
    sortServer();
    processing();
    mapping();
    splic();

    // cout << result;
	totalCost = purchaseCost + dailyCost;

#ifdef TEST
	int migTime = 0;
	for(int i = 0; i < days; i++) {
		migTime += migrateResult[i].size();
	}
	cout << "server num = " << serverID << endl;
	cout << "migration times: " << migTime << endl;
    cout << "total cost: " << totalCost << ", purchase cost: " << purchaseCost << ", daily cost: " << dailyCost << endl;
	cout << "invalid migration: " << number << endl;
#endif
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853

复赛正式赛代码

#include <bits/stdc++.h>
using namespace std;

// #define TEST
int D = 1;
int number = 0; // 无效迁移次数
int day = 0;

struct serverTemplate {
    serverTemplate(){}
    serverTemplate(string type, int core, int mem, int price, int cost){
        this->type = type;
        this->core = core;
        this->mem = mem;
        this->price = price;
        this->cost = cost;
    }
    string type;
    int core;
    int mem;
    int price;
    int cost;
};

struct server {
    server(){}
    server(serverTemplate st, int id){
        this->st = st;
        this->coreA = st.core/2;
        this->coreB = st.core/2;
        this->memA = st.mem/2;
        this->memB = st.mem/2;
        this->id = id;
    }
    serverTemplate st;
    int id;
    int coreA;
    int coreB;
    int memA;
    int memB;
};

struct VMware {
    VMware(){}
    VMware(int core, int mem, int binode) {
        this->core = core;
        this->mem = mem;
        this->binode = binode;
    }
    int core;       // 核心数
    int mem;        // 内存
    int binode;     // 是否双节点部署
};

struct inform {
    inform(){}
    inform(string _st, int _id, string _ed) {
        st = _st;
        id = _id;
        ed = _ed;
    }
    string st;
    int id;
    string ed;
};

/* ------------------------------服务器部署所需信息------------------------------ */
// 天数, 服务器类型数, 虚拟机类型数
int days, predays, serverKind, VMwareKind;
int serverID = 0, VMwareNum = 0, serverIDWait = 0;
// 服务器型号表
unordered_map<string, serverTemplate> serverTable;
// 将服务器按照成本排序
vector<serverTemplate> orderedServer;
// 虚拟机型号表
unordered_map<string, VMware> VMwareTable;
// 已购买服务器集群
vector<server> serverCluster;
vector<server> serverClusterWait;
// 虚拟机ID对照表
unordered_map<int, VMware> VMwareCluster;
unordered_map<int, string> VMwareIDtoStr;
// 每天的请求信息
vector<vector<pair<int, int>>> quest;
// 记录虚拟机运行在哪个服务器的哪个节点上
unordered_map<int, pair<int, int>> VMwareOnServer;
// 当前开机服务器, 表示上面部署了多少台虚拟机
vector<list<int>> serverRun;
vector<list<int>> serverRunWait;


// 每天添加的服务器对应的ID以及排序后的映射
vector<vector<pair<string, int>>> befSer2ID;
unordered_map<int, string> aftMapping;
// 记录每一天增加的每种服务器的数量
vector<vector<pair<string, int>>> serDayNum;
// 记录每天的虚拟机部署情况
vector<vector<inform>> dayResult;
// 记录每天的虚拟机迁移情况
vector<vector<inform>> migrateResult;
// 记录虚拟机删除的日期
unordered_map<int, int> deleteDay;
// 记录虚拟机添加的日期
unordered_map<int, int> addDay;
// 每天的添加删除次数
vector<vector<int>> addDelTimes;
int maxAddTimes = 0, initMaxAdd = 0;
// 输出字符串
vector<string> result;
// 待迁移的虚拟机
vector<int> vmwareVec;
// 待迁移的虚拟机信息
unordered_map<int, pair<int, int>> vmwareOnVec;

// 记录当天创建当天删除的部署在新服务器上的虚拟机
vector<int> vmAddDelSameDay;
// 成本
long long purchaseCost, dailyCost, totalCost;
int serNumDay;
int totalCore, totalMem;

int a = 2, b = 1;	// 评价函数的系数

void readInfo() {
    /* 读取并保存服务器信息--------------------------- */
    cin >> serverKind;
    string typeStr, coreStr, memStr, priceStr, costStr;
    for(int i = 0; i < serverKind; i++) {
        cin >> typeStr >> coreStr >> memStr >> priceStr >> costStr;
        string _typeStr;
        _typeStr = typeStr.substr(1, typeStr.size()-2);

        int _core = 0, _mem = 0, _price = 0, _cost = 0;
        _core = stoi(coreStr.substr(0, coreStr.size()-1));
        _mem = stoi(memStr.substr(0, memStr.size()-1));
        _price = stoi(priceStr.substr(0, priceStr.size()-1));
        _cost = stoi(costStr.substr(0, costStr.size()-1));

        serverTable[_typeStr] = serverTemplate(_typeStr, _core, _mem, _price, _cost);
		orderedServer.push_back(serverTable[_typeStr]);
    }
    /* 读取并保存虚拟机信息--------------------------- */
    cin >> VMwareKind;
    string VMtypeStr, VMcoreStr, VMmemStr, VMbinode;
    for(int i = 0; i < VMwareKind; i++) {
        cin >> VMtypeStr >> VMcoreStr >> VMmemStr >> VMbinode;
        string _VMtypeStr;
        _VMtypeStr = VMtypeStr.substr(1, VMtypeStr.size()-2);

        int _VMcore = 0, _VMmem = 0, _VMbinode = 0;
        _VMcore = stoi(VMcoreStr.substr(0, VMcoreStr.size()-1));
        _VMmem = stoi(VMmemStr.substr(0, VMmemStr.size()-1));
        if(VMbinode[0] == '1') {
            _VMbinode = 1;
        } else {
            _VMbinode = 0;
        }
        VMwareTable[_VMtypeStr] = VMware(_VMcore, _VMmem, _VMbinode);
		
    }
    /* 读取并保存用户请求信息--------------------------- */
    cin >> days >> predays;
    befSer2ID.resize(days);
    serDayNum.resize(days);
    dayResult.resize(days);
    migrateResult.resize(days);
	addDelTimes.resize(days, vector<int>(2, 0));
}

// serverTemplate按照成本比较
bool cmp1(serverTemplate &s1, serverTemplate &s2) {
    return s1.cost < s2.cost;
}
// serverTemplate按照售价比较
bool ccmp1(serverTemplate &s1, serverTemplate &s2) {
    return s1.price < s2.price;
}

// 对服务器排序
void sortServer() {
	sort(orderedServer.begin(), orderedServer.end(), cmp1);
}

// 部署
void chooseServer(server &_server, int VMwareIdx, int deployNode) {
    int serverIdx = _server.id;
    auto &_VMware = VMwareCluster[VMwareIdx];
    // 如果是双节点部署
    if(deployNode == 2) {
        _server.coreA -= _VMware.core/2;
        _server.coreB -= _VMware.core/2;
        _server.memA -= _VMware.mem/2;
        _server.memB -= _VMware.mem/2;
        VMwareOnServer[VMwareIdx] = make_pair(serverIdx, 2);
    }
    // 如果是A节点部署
    else if(deployNode == 0) {
        _server.coreA -= _VMware.core;
        _server.memA -= _VMware.mem;
        VMwareOnServer[VMwareIdx] = make_pair(serverIdx, 0);
    }
    // 如果为B节点部署
    else {
        _server.coreB -= _VMware.core;
        _server.memB -= _VMware.mem;
        VMwareOnServer[VMwareIdx] = make_pair(serverIdx, 1);
    }
}

// trick
int haveFreeSpace(server &_server, VMware &vm) {

    if (vm.binode == 1) {
        if (9*_server.coreA >= 10*vm.core/2 && 9*_server.memA >= 10*vm.mem/2) {
            return 2;
        }
    } else {
        if (9*_server.coreA >= 10*vm.core && 9*_server.memA >= 10*vm.mem) {
			return 0;
        }
    }
    return -1;
}

// 处理add请求
void createVMware(int VMID, int day) {
    // 获取该虚拟机信息
    VMware &_VMware = VMwareCluster[VMID];
	int idx = -1, deployNode = -1;
	int minScore = INT_MAX;

    if(_VMware.binode == 1) {
        // 先在已有服务器上找
        for(int i = 0; i < serverCluster.size(); i++) {
            auto &_server = serverCluster[i];
			int score = INT_MAX, node = -1;
			if(2*_server.coreA >= _VMware.core && 2*_server.memA >= _VMware.mem && 2*_server.coreB >= _VMware.core && 2*_server.memB >= _VMware.mem) {
				score = min(a*_server.coreA-_VMware.core+b*(_server.memA-_VMware.mem/2), a*_server.coreB-_VMware.core+b*(_server.memB-_VMware.mem/2));
				node = 2;
			}
			if(node != -1 && score < minScore) {
				minScore = score;
				idx = i;
				deployNode = node;
				// break;
			}
        }
        // 如果找到了
        if(idx != -1) {
            auto &_s = serverCluster[idx];
            chooseServer(_s, VMID, deployNode);
            serverRun[_s.id].push_back(VMID);
            assert(_s.coreA >= 0 && _s.coreB >= 0 && _s.memA >= 0 && _s.memB >= 0);
            assert(_s.coreA <= _s.st.core/2 && _s.coreB <= _s.st.core/2 && _s.memA <= _s.st.mem/2 && _s.memB <= _s.st.mem/2);
            return;
        }
        // 再在待购买区找
        for(int i = 0; i < serverClusterWait.size(); i++) {
            auto &_server = serverClusterWait[i];
            int score = INT_MAX, node = -1;
			if(2*_server.coreA >= _VMware.core && 2*_server.memA >= _VMware.mem && 2*_server.coreB >= _VMware.core && 2*_server.memB >= _VMware.mem) {
				score = min(a*_server.coreA-_VMware.core+b*(_server.memA-_VMware.mem/2), a*_server.coreB-_VMware.core+b*(_server.memB-_VMware.mem/2));
				node = 2;
			}
			if(node != -1 && score < minScore) {
				minScore = score;
				idx = i;
				deployNode = node;
				// break;
			}
        }
        // 如果找到了
        if(idx != -1) {
            auto &_s = serverClusterWait[idx];
            chooseServer(_s, VMID, deployNode);
            serverRunWait[_s.id].push_back(VMID);
            assert(_s.coreA >= 0 && _s.coreB >= 0 && _s.memA >= 0 && _s.memB >= 0);
            assert(_s.coreA <= _s.st.core/2 && _s.coreB <= _s.st.core/2 && _s.memA <= _s.st.mem/2 && _s.memB <= _s.st.mem/2);
            return;
        }
    }
    else {
        for(int i = 0; i < serverCluster.size(); i++) {
			auto &_server = serverCluster[i];
			int score = INT_MAX, node = -1;
			if(_server.coreA >= _VMware.core && _server.memA >= _VMware.mem) {
				score = a*(_server.coreA-_VMware.core)+b*(_server.memA-_VMware.mem);
				node = 0;
			}
			if(_server.coreB >= _VMware.core && _server.memB >= _VMware.mem) {
				int tmp = a*(_server.coreB-_VMware.core)+b*(_server.memB-_VMware.mem);
				// if(tmp < score) {
				if((score == INT_MAX) || (score != INT_MAX && tmp > score)) {
					score = tmp;
					node = 1;
				}
			}
			if(node != -1 && score < minScore) {
				minScore = score;
				idx = i;
				deployNode = node;
				// break;
			}
		}
        // 如果找到了
        if(idx != -1) {
            auto &_s = serverCluster[idx];
            chooseServer(_s, VMID, deployNode);
            serverRun[_s.id].push_back(VMID);
            assert(_s.coreA >= 0 && _s.coreB >= 0 && _s.memA >= 0 && _s.memB >= 0);
            assert(_s.coreA <= _s.st.core/2 && _s.coreB <= _s.st.core/2 && _s.memA <= _s.st.mem/2 && _s.memB <= _s.st.mem/2);
            return;
        }
        for(int i = 0; i < serverClusterWait.size(); i++) {
			auto &_server = serverClusterWait[i];
			int score = INT_MAX, node = -1;
			if(_server.coreA >= _VMware.core && _server.memA >= _VMware.mem) {
				score = a*(_server.coreA-_VMware.core)+b*(_server.memA-_VMware.mem);
				node = 0;
			}
			if(_server.coreB >= _VMware.core && _server.memB >= _VMware.mem) {
				int tmp = a*(_server.coreB-_VMware.core)+b*(_server.memB-_VMware.mem);
				// if(tmp < score) {
				if((score == INT_MAX) || (score != INT_MAX && tmp > score)) {
					score = tmp;
					node = 1;
				}
			}
			if(node != -1 && score < minScore) {
				minScore = score;
				idx = i;
				deployNode = node;
				// break;
			}
		}
        // 如果找到了
        if(idx != -1) {
            auto &_s = serverClusterWait[idx];
            chooseServer(_s, VMID, deployNode);
            serverRunWait[_s.id].push_back(VMID);
            assert(_s.coreA >= 0 && _s.coreB >= 0 && _s.memA >= 0 && _s.memB >= 0);
            assert(_s.coreA <= _s.st.core/2 && _s.coreB <= _s.st.core/2 && _s.memA <= _s.st.mem/2 && _s.memB <= _s.st.mem/2);
            return;
        }
    }

    for(auto &st : orderedServer) {
        auto s = server(st, -1);
        // 如果服务器合适，选择该服务器
		int node = haveFreeSpace(s, _VMware);
        if(node != -1) {
			s.id = serverClusterWait.size();
			serverClusterWait.push_back(s);
			// 重新部署
			chooseServer(serverClusterWait.back(), VMID, node);
			serverRunWait.push_back(list<int>{VMID});
			assert(serverClusterWait.back().coreA >= 0 && serverClusterWait.back().coreB >= 0 && serverClusterWait.back().memA >= 0 && serverClusterWait.back().memB >= 0);
			return;
        }
    }
}

// 删除请求
void delVMware(int VMID) {
    int serverIdx = VMwareOnServer[VMID].first;
    serverRun[serverIdx].remove(VMID);
    // 释放对应的server上的资源占用情况
    auto &_server = serverCluster[serverIdx];

	if(VMwareOnServer[VMID].second == 2) {
        _server.coreA += VMwareCluster[VMID].core/2;
        _server.coreB += VMwareCluster[VMID].core/2;
        _server.memA += VMwareCluster[VMID].mem/2;
        _server.memB += VMwareCluster[VMID].mem/2;
    }
    else {
        if(VMwareOnServer[VMID].second == 0) {
            _server.coreA += VMwareCluster[VMID].core;
            _server.memA += VMwareCluster[VMID].mem;
        }
        else {
            _server.coreB += VMwareCluster[VMID].core;
            _server.memB += VMwareCluster[VMID].mem;
        }
    }

    VMwareOnServer.erase(VMID);
}

// 服务器合并，A+A
void serverMerge() {
	if(serverClusterWait.empty()) return;
    vector<server> temp; // 存服务器
    vector<list<int>> tempRun;	// 存服务器上的虚拟机
    // 第几个服务器
    int i = 0;
    while(i+1 < serverClusterWait.size()) {
        int coreA = serverClusterWait[i].st.core/2 - serverClusterWait[i].coreA + serverClusterWait[i+1].st.core/2 - serverClusterWait[i+1].coreA;
        int coreB = serverClusterWait[i].st.core/2 - serverClusterWait[i].coreB + serverClusterWait[i+1].st.core/2 - serverClusterWait[i+1].coreB;
        int memA = serverClusterWait[i].st.mem/2 - serverClusterWait[i].memA   + serverClusterWait[i+1].st.mem/2 - serverClusterWait[i+1].memA;
        int memB = serverClusterWait[i].st.mem/2 - serverClusterWait[i].memB   + serverClusterWait[i+1].st.mem/2 - serverClusterWait[i+1].memB;
        int price = serverClusterWait[i].st.price + serverClusterWait[i+1].st.price;
        int cost = serverClusterWait[i].st.cost + serverClusterWait[i+1].st.cost;
		
        int s;
        for(s = 0; s < orderedServer.size(); s++) {
            auto &st = orderedServer[s];
            // 如果存在性价比更高的大服务器
            if(st.price < price && st.cost < cost && st.core/2 >= coreA && st.core/2 >= coreB && st.mem/2 >= memA && st.mem/2 >= memB) {
                // 进行转移
                server _server = server(st, -1);
                _server.coreA -= coreA;
                _server.coreB -= coreB;
                _server.memA -= memA;
                _server.memB -= memB;
				assert(_server.coreA >= 0 && _server.coreB >= 0 && _server.memA >= 0 && _server.memB >= 0);
                temp.push_back(_server);
                list<int> lst = serverRunWait[i];
                for(auto &VMID : serverRunWait[i+1]) {
                    lst.push_back(VMID);
                }
                tempRun.push_back(lst);
                i += 2;
                break;
            }
        }
        if(s == orderedServer.size()) {
            // 找不到更好的，就将第i个转移到temp中
            temp.push_back(serverClusterWait[i]);
            tempRun.push_back(serverRunWait[i]);
            i++;
        }
    }
    if(i == serverClusterWait.size()-1) {
        // 找不到更好的，就将第i个转移到temp中
        temp.push_back(serverClusterWait[i]);
        tempRun.push_back(serverRunWait[i]);
    }
	
    // 重新部署，并更新信息
    for(int ii = 0; ii < temp.size(); ii++) {
        server &s = temp[ii];
        befSer2ID[day].push_back(make_pair(s.st.type, serverID));
        s.id = serverID;
        serverCluster.push_back(s);
        purchaseCost += s.st.price;
        serverRun.push_back(tempRun[ii]);
        // 更新虚拟机的部署信息
        for(auto &VMID : serverRun.back()) {
            VMwareOnServer[VMID].first = serverID;
        }
        assert(serverCluster[serverID].coreA >= 0 && serverCluster[serverID].coreB >= 0 && serverCluster[serverID].memA >= 0 && serverCluster[serverID].memB >= 0);
        serverID++;
    }
}

// 对请求按照占用资源大小降序排序
bool cmp4(pair<int, int> &p1, pair<int, int> &p2) {
	int vmid1 = p1.second;
	int vmid2 = p2.second;
	return VMwareCluster[vmid1].core+VMwareCluster[vmid1].mem > VMwareCluster[vmid2].core+VMwareCluster[vmid2].mem;
}

// 处理第day天的请求
void serverAllocation(int day) {
	serNumDay = serverID;
	vector<pair<int, int>> request;

	vector<pair<int, int>> request1;
	vector<pair<int, int>> request2;
	for(auto req : quest[day]) {
		if(req.first == 1) {
			request1.push_back(req);
		}
		else {
			request2.push_back(req);
		}
	}
	sort(request1.begin(), request1.end(), cmp4);
	

    serverClusterWait.clear();
    serverRunWait.clear();

    // 处理请求信息
	for(int i = 0; i < request1.size(); i++) {
		auto &req = request1[i];
        int VMID = req.second;
        createVMware(VMID, day);

        VMwareNum++;
    }
    // 进行服务器合并
    serverMerge();
	
    for(int i = 0; i < request2.size(); i++) {
		auto &req = request2[i];
        int VMID = req.second;
        delVMware(VMID);
        VMwareNum--;
    }

	// 保存部署信息
	for(int i = 0; i < quest[day].size(); i++) {
		auto &req = quest[day][i];
        // 如果是add
        if(req.first == 1) {
            int VMID = req.second;
            if(VMwareOnServer[VMID].second == 0) dayResult[day].push_back(inform("(", VMwareOnServer[VMID].first, ", A)\n"));
			else if(VMwareOnServer[VMID].second == 1) dayResult[day].push_back(inform("(", VMwareOnServer[VMID].first, ", B)\n"));
			else dayResult[day].push_back(inform("(", VMwareOnServer[VMID].first, ")\n"));
        }
    }
}

// 对每天购买的服务器按照型号进行排序，方便后面ID映射
bool mycmp(pair<string, int> &a, pair<string, int> &b) {
    return a.first < b.first;
}

// 服务器ID映射第i天
void mapping(int i) {
    // 记录起始数字
    if(befSer2ID[i].empty()) return;
    int st = befSer2ID[i][0].second;
    // 排序
    sort(befSer2ID[i].begin(), befSer2ID[i].end(), mycmp);
    // 映射
    for(int j = 0; j < befSer2ID[i].size(); j++) {
        auto &temp = befSer2ID[i][j];
        aftMapping[temp.second] = to_string(st);
        st++;
        // 按顺序统计出现次数，方便后面输出
        if(j == 0) {
            serDayNum[i].push_back(make_pair(befSer2ID[i][j].first, 1));
        } else {
            if(befSer2ID[i][j].first == serDayNum[i].back().first) {
                serDayNum[i].back().second++;
            } else {
                serDayNum[i].push_back(make_pair(befSer2ID[i][j].first, 1));
            }
        }
    }
}

// 组合输出第i天字符串
void splic(int i) {
    result.clear();
    // 先拼接购买信息
    int num = serDayNum[i].size();
    result.push_back("(purchase, " + to_string(num) + ")\n");
    if(num != 0) {
        for(int j = 0; j < num; j++) {
            result.push_back("(" + serDayNum[i][j].first + ", " + to_string(serDayNum[i][j].second) + ")\n");
        }
    }
    // 再拼接迁移信息
    if(migrateResult[i].size() == 0) result.push_back("(migration, 0)\n");
    else {
        result.push_back("(migration, " + to_string(migrateResult[i].size()) + ")\n");
        for(int j = 0; j < migrateResult[i].size(); j++) {
            auto &mig = migrateResult[i][j];
			string res;
            res += mig.st;
            res += aftMapping[mig.id];
            res += mig.ed;
			result.push_back(res);
        }
    }
    // 再拼接部署信息
    for(int j = 0; j < dayResult[i].size(); j++) {
        auto &info = dayResult[i][j];
		string res;
        res += info.st;
        res += aftMapping[info.id];
        res += info.ed;
		result.push_back(res);
    }
    // 输出
	for(auto &s : result) {
		cout << s;
	}
    // cout << result;
	fflush(stdout);
}

// 日耗
void serverCost() {
    for(int i = 0; i < serverID; i++) {
        if(serverRun[i].size()) {
            dailyCost += serverCluster[i].st.cost;
        }
    }
}

// 负载率比较函数
bool cmp5(server &s1, server &s2) {
	// double radio1 = pow(1.0*(s1.st.core-s1.coreA-s1.coreB)/s1.st.core, 2)+pow(1.0*(s1.st.mem-s1.memA-s1.memB)/s1.st.mem, 2);
	// double radio2 = pow(1.0*(s2.st.core-s2.coreA-s2.coreB)/s2.st.core, 2)+pow(1.0*(s2.st.mem-s2.memA-s2.memB)/s2.st.mem, 2);
	// double radio1 = 1.0*(s1.st.core-s1.coreA-s1.coreB + s1.st.mem-s1.memA-s1.memB)/(s1.st.core + s1.st.mem);
	// double radio2 = 1.0*(s2.st.core-s2.coreA-s2.coreB + s2.st.mem-s2.memA-s1.memB)/(s2.st.core + s2.st.mem);
	double radio1 = 1.0*(s1.st.core-s1.coreA-s1.coreB)/s1.st.core + 1.0*(s1.st.mem-s1.memA-s1.memB)/s1.st.mem;
	double radio2 = 1.0*(s2.st.core-s2.coreA-s2.coreB)/s2.st.core + 1.0*(s2.st.mem-s2.memA-s2.memB)/s2.st.mem;
	
	return radio1 < radio2;
}

// 按照服务器上的虚拟机个数比较
bool ccmp5(server &s1, server &s2) {
	return serverRun[s1.id].size() < serverRun[s2.id].size();
}

// 迁移
void migration(int day) {
	
	int times;
	if(addDelTimes[day-1][1] > 1000 && D == 1) {
		times = VMwareNum;
		D = 0;
	}
	else {
		times = 3*VMwareNum/100;
	}
	if(times == 0) return;

	double target = 1.0;
	int p = 6;
	while(p > 0) {
		p--;
		target -= 0.002;

		vmwareVec.clear();
		vmwareOnVec.clear();
		
		vector<server> tmp;
		
		for(int i = 0; i < serverID; i++) {
			auto &_server = serverCluster[i];
			double radio = (1.0*(_server.st.core-_server.coreA-_server.coreB)/_server.st.core + 1.0*(_server.st.mem-_server.memA-_server.memB)/_server.st.mem)/2;
			if(radio > target) {
				continue;
			}
			else if(serverRun[i].size() > 0) tmp.push_back(_server);
		}
		
		sort(tmp.begin(), tmp.end(), ccmp5);
		// 记录迁移不动的虚拟机类型
		unordered_map<string, bool> book;
		for(int i = 0; i < tmp.size(); i++) {
			int id = tmp[i].id;
			auto &_server = serverCluster[id];

			int n = 2;
			for(auto VMID : serverRun[id]) {
				if(deleteDay[VMID] == day) continue;
				vmwareVec.push_back(VMID);
				book[VMwareIDtoStr[VMID]] = false;
				vmwareOnVec[VMID] = VMwareOnServer[VMID];
				n--;
				if(n <= 0) break;
			}
		}

		for(int i = 0; i < vmwareVec.size() ; i++) {
			int VMID = vmwareVec[i];
			// 如果之前迁移不动，就continue
			if(book[VMwareIDtoStr[VMID]] == true) continue;
			VMware &_VMware = VMwareCluster[VMID];
			// 原来处于的服务器ID
			int serID = vmwareOnVec[VMID].first;
			auto &_server = serverCluster[serID];
			// 原来的服务器的负载率
			double initRadio = (1.0*(_server.st.core-_server.coreA-_server.coreB)/_server.st.core + 1.0*(_server.st.mem-_server.memA-_server.memB)/_server.st.mem)/2;
			if(initRadio > target) continue;
			
			delVMware(VMID);
			
			int idx = -1, deployNode = -1;
			int minScore = INT_MAX;
			
			if(_VMware.binode == 1) {
				for(int i = 0; i < serverID; i++) {
					int id = i;
					auto &_server = serverCluster[id];
					int score = INT_MAX, node = -1;
					if(2*_server.coreA >= _VMware.core && 2*_server.memA >= _VMware.mem && 2*_server.coreB >= _VMware.core && 2*_server.memB >= _VMware.mem) {
						score = min(a*_server.coreA-_VMware.core+b*(_server.memA-_VMware.mem/2), a*_server.coreB-_VMware.core+b*(_server.memB- _VMware.mem/2));
						node = 2;
					}
					if(node != -1 && score < minScore) {
						minScore = score;
						idx = id;
						deployNode = node;
					}
				}
			} else {
				for(int i = 0; i < serverID; i++) {
					int id = i;
					auto &_server = serverCluster[id];
					int score = INT_MAX, node = -1;
					if(_server.coreA >= _VMware.core && _server.memA >= _VMware.mem) {
						score = a*(_server.coreA-_VMware.core)+b*(_server.memA-_VMware.mem);
						node = 0;
					}
					if(_server.coreB >= _VMware.core && _server.memB >= _VMware.mem) {
						int tmp = a*(_server.coreB-_VMware.core)+b*(_server.memB-_VMware.mem);
						// if(tmp < score) {
						if((score == INT_MAX) || (score != INT_MAX && tmp > score)) {
							score = tmp;
							node = 1;
						}
					}
					if(node != -1 && score < minScore) {
						minScore = score;
						idx = id;
						deployNode = node;
					}
				}
			}
			
			if(idx != -1) {
				if(idx != serID && serverRun[idx].empty()) {
					idx = serID;
					deployNode = vmwareOnVec[VMID].second;
				}
				auto &_s = serverCluster[idx];
				chooseServer(_s, VMID, deployNode);
				serverRun[_s.id].push_back(VMID);
				if(vmwareOnVec[VMID] == VMwareOnServer[VMID]) {
					book[VMwareIDtoStr[VMID]] = true;
				}
				if(vmwareOnVec[VMID] != VMwareOnServer[VMID]) {
					if(deployNode == 0) {
						migrateResult[day].push_back(inform("("+to_string(VMID)+", ", _s.id, ", A)\n"));
					} else if(deployNode == 1) {
						migrateResult[day].push_back(inform("("+to_string(VMID)+", ", _s.id, ", B)\n"));
					} else {
						migrateResult[day].push_back(inform("("+to_string(VMID)+", ", _s.id, ")\n"));
					}
					times--;
				} else {
					number++;
				}
			}
			if(times <= 0) return;
		}
		if(times <= 0) return;
	}
}

void processing() {
    // 迁移
	if(day != 0) migration(day);
	
    // 处理请求
    serverAllocation(day);
    // 日耗
    serverCost();
    // ID映射
    mapping(day);
    // 输出
    splic(day);

    day++;
}


int main(int argc, char* argv[]) {
    // string s(argv[1]);
	// string filePath = "./data/training-" + s + ".txt";
    // freopen(filePath.c_str(),"rb",stdin);

    readInfo();
    sortServer();
    for(int t = 0; t < days; t++) {
        if(t == 50*days/100+1) {
            sort(orderedServer.begin(), orderedServer.end(), ccmp1);
        }
        string opera, VMtype, VMID;
        vector<pair<int, int>> questTemp;
        int n;  // 每天n个请求
        cin >> n;
        for(int i = 0; i < n; i++) {
            // 先读取请求类型
            cin >> opera;
            // 格式化后的请求类型， 虚拟机型号，虚拟机ID
            string _opera, _VMtype, _VMID;
            // 如果是添加请求
            if(opera[1] == 'a') {
                cin >> VMtype >> VMID;
                _opera = opera.substr(1, opera.size() - 2);
                _VMtype = VMtype.substr(0, VMtype.size() - 1);
                _VMID = VMID.substr(0, VMID.size() - 1);
                VMwareCluster[stoi(_VMID)] = VMwareTable[_VMtype];
				VMwareIDtoStr[stoi(_VMID)] = _VMtype;
                addDelTimes[t][0]++; // 添加次数
            }
            // 如果是删除请求，表明删除已有虚拟机
            else {
                cin >> VMID;
                _opera = opera.substr(1, opera.size() - 2);
                _VMID = VMID.substr(0, VMID.size() - 1);
                addDelTimes[t][1]++; // 删除次数
                deleteDay[stoi(_VMID)] = t;
            }
            // 记录下此时的请求类型和ID
            if(_opera == "add") questTemp.push_back(make_pair(1, stoi(_VMID)));
			else questTemp.push_back(make_pair(0, stoi(_VMID)));
        }
        // 将当天请求保存下来
		quest.push_back(questTemp);
        processing();
    }
#ifdef TEST
	int migTime = 0;
	for(int i = 0; i < days; i++) {
		migTime += migrateResult[i].size();
	}
	totalCost = purchaseCost + dailyCost;
	cout << "server num = " << serverID << endl;
	cout << "migration times: " << migTime << endl;
    cout << "total cost: " << totalCost << ", purchase cost: " << purchaseCost << ", daily cost: " << dailyCost << endl;
	cout << "invalid migration: " << number << endl;

#endif

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828

决赛正式赛代码

#include <bits/stdc++.h>
using namespace std;

// #define TEST
int D = 1;
int number = 0; // 无效迁移次数
int day = 0;

struct serverTemplate {
    serverTemplate(){}
    serverTemplate(string type, int core, int mem, int price, int cost){
        this->type = type;
        this->core = core;
        this->mem = mem;
        this->price = price;
        this->cost = cost;
    }
    string type;
    int core;
    int mem;
    int price;
    int cost;
};

struct server {
    server(){}
    server(serverTemplate st, int id){
        this->st = st;
        this->coreA = st.core/2;
        this->coreB = st.core/2;
        this->memA = st.mem/2;
        this->memB = st.mem/2;
        this->id = id;
    }
    serverTemplate st;
    int id;
    int coreA;
    int coreB;
    int memA;
    int memB;
};

struct VMware {
    VMware(){}
    VMware(int core, int mem, int binode) {
        this->core = core;
        this->mem = mem;
        this->binode = binode;
    }
    int core;       // 核心数
    int mem;        // 内存
    int binode;     // 是否双节点部署
};

struct inform {
    inform(){}
    inform(string _st, int _id, string _ed) {
        st = _st;
        id = _id;
        ed = _ed;
    }
    string st;
    int id;
    string ed;
};

/* ------------------------------服务器部署所需信息------------------------------ */
// 天数, 服务器类型数, 虚拟机类型数
int days, predays, serverKind, VMwareKind;
int serverID = 0, VMwareNum = 0, serverIDWait = 0;
// 服务器型号表
unordered_map<string, serverTemplate> serverTable;
// 将服务器按照成本排序
vector<serverTemplate> orderedServer;
// 虚拟机型号表
unordered_map<string, VMware> VMwareTable;
// 已购买服务器集群
vector<server> serverCluster;
vector<server> serverClusterWait;
// 虚拟机ID对照表
unordered_map<int, VMware> VMwareCluster;
unordered_map<int, string> VMwareIDtoStr;
// 每天的请求信息
vector<vector<pair<int, int>>> quest;
// 记录虚拟机运行在哪个服务器的哪个节点上
unordered_map<int, pair<int, int>> VMwareOnServer;
// 当前开机服务器, 表示上面部署了多少台虚拟机
vector<list<int>> serverRun;
vector<list<int>> serverRunWait;


// 每天添加的服务器对应的ID以及排序后的映射
vector<vector<pair<string, int>>> befSer2ID;
unordered_map<int, string> aftMapping;
// 记录每一天增加的每种服务器的数量
vector<vector<pair<string, int>>> serDayNum;
// 记录每天的虚拟机部署情况
vector<vector<inform>> dayResult;
// 记录每天的虚拟机迁移情况
vector<vector<inform>> migrateResult;
// 记录虚拟机删除的日期
unordered_map<int, int> deleteDay;
// 记录虚拟机添加的日期
unordered_map<int, int> addDay;
// 每天的添加删除次数
vector<vector<int>> addDelTimes;
int maxAddTimes = 0, initMaxAdd = 0;
// 输出字符串
vector<string> result;
// 待迁移的虚拟机
vector<int> vmwareVec;
// 待迁移的虚拟机信息
unordered_map<int, pair<int, int>> vmwareOnVec;

// 记录当天创建当天删除的部署在新服务器上的虚拟机
vector<int> vmAddDelSameDay;
// 成本
long long purchaseCost, dailyCost, totalCost;
int serNumDay;
int totalCore, totalMem;

int a = 2, b = 1;	// 评价函数的系数

void readInfo() {
    /* 读取并保存服务器信息--------------------------- */
    cin >> serverKind;
    string typeStr, coreStr, memStr, priceStr, costStr;
    for(int i = 0; i < serverKind; i++) {
        cin >> typeStr >> coreStr >> memStr >> priceStr >> costStr;
        string _typeStr;
        _typeStr = typeStr.substr(1, typeStr.size()-2);

        int _core = 0, _mem = 0, _price = 0, _cost = 0;
        _core = stoi(coreStr.substr(0, coreStr.size()-1));
        _mem = stoi(memStr.substr(0, memStr.size()-1));
        _price = stoi(priceStr.substr(0, priceStr.size()-1));
        _cost = stoi(costStr.substr(0, costStr.size()-1));

        serverTable[_typeStr] = serverTemplate(_typeStr, _core, _mem, _price, _cost);
		orderedServer.push_back(serverTable[_typeStr]);
    }
    /* 读取并保存虚拟机信息--------------------------- */
    cin >> VMwareKind;
    string VMtypeStr, VMcoreStr, VMmemStr, VMbinode;
    for(int i = 0; i < VMwareKind; i++) {
        cin >> VMtypeStr >> VMcoreStr >> VMmemStr >> VMbinode;
        string _VMtypeStr;
        _VMtypeStr = VMtypeStr.substr(1, VMtypeStr.size()-2);

        int _VMcore = 0, _VMmem = 0, _VMbinode = 0;
        _VMcore = stoi(VMcoreStr.substr(0, VMcoreStr.size()-1));
        _VMmem = stoi(VMmemStr.substr(0, VMmemStr.size()-1));
        if(VMbinode[0] == '1') {
            _VMbinode = 1;
        } else {
            _VMbinode = 0;
        }
        VMwareTable[_VMtypeStr] = VMware(_VMcore, _VMmem, _VMbinode);
		
    }
    /* 读取并保存用户请求信息--------------------------- */
    cin >> days >> predays;
    befSer2ID.resize(days);
    serDayNum.resize(days);
    dayResult.resize(days);
    migrateResult.resize(days);
	addDelTimes.resize(days, vector<int>(2, 0));
}

// serverTemplate按照成本比较
bool cmp1(serverTemplate &s1, serverTemplate &s2) {
    return s1.cost < s2.cost;
}
// serverTemplate按照售价比较
bool ccmp1(serverTemplate &s1, serverTemplate &s2) {
    return s1.price < s2.price;
}

// 对服务器排序
void sortServer() {
	sort(orderedServer.begin(), orderedServer.end(), cmp1);
}

// 部署
void chooseServer(server &_server, int VMwareIdx, int deployNode) {
    int serverIdx = _server.id;
    auto &_VMware = VMwareCluster[VMwareIdx];
    // 如果是双节点部署
    if(deployNode == 2) {
        _server.coreA -= _VMware.core/2;
        _server.coreB -= _VMware.core/2;
        _server.memA -= _VMware.mem/2;
        _server.memB -= _VMware.mem/2;
        VMwareOnServer[VMwareIdx] = make_pair(serverIdx, 2);
    }
    // 如果是A节点部署
    else if(deployNode == 0) {
        _server.coreA -= _VMware.core;
        _server.memA -= _VMware.mem;
        VMwareOnServer[VMwareIdx] = make_pair(serverIdx, 0);
    }
    // 如果为B节点部署
    else {
        _server.coreB -= _VMware.core;
        _server.memB -= _VMware.mem;
        VMwareOnServer[VMwareIdx] = make_pair(serverIdx, 1);
    }
}

// trick
int haveFreeSpace(server &_server, VMware &vm) {

    if (vm.binode == 1) {
        if (9*_server.coreA >= 10*vm.core/2 && 9*_server.memA >= 10*vm.mem/2) {
            return 2;
        }
    } else {
        if (9*_server.coreA >= 10*vm.core && 9*_server.memA >= 10*vm.mem) {
			return 0;
        }
    }
    return -1;
}

// 处理add请求
void createVMware(int VMID, int day) {
    // 获取该虚拟机信息
    VMware &_VMware = VMwareCluster[VMID];
	int idx = -1, deployNode = -1;
	int minScore = INT_MAX;

    if(_VMware.binode == 1) {
        // 先在已有服务器上找
        for(int i = 0; i < serverCluster.size(); i++) {
            auto &_server = serverCluster[i];
			int score = INT_MAX, node = -1;
			if(2*_server.coreA >= _VMware.core && 2*_server.memA >= _VMware.mem && 2*_server.coreB >= _VMware.core && 2*_server.memB >= _VMware.mem) {
				score = min(a*_server.coreA-_VMware.core+b*(_server.memA-_VMware.mem/2), a*_server.coreB-_VMware.core+b*(_server.memB-_VMware.mem/2));
				node = 2;
			}
			if(node != -1 && score < minScore) {
				minScore = score;
				idx = i;
				deployNode = node;
				// break;
			}
        }
        // 如果找到了
        if(idx != -1) {
            auto &_s = serverCluster[idx];
            chooseServer(_s, VMID, deployNode);
            serverRun[_s.id].push_back(VMID);
            assert(_s.coreA >= 0 && _s.coreB >= 0 && _s.memA >= 0 && _s.memB >= 0);
            assert(_s.coreA <= _s.st.core/2 && _s.coreB <= _s.st.core/2 && _s.memA <= _s.st.mem/2 && _s.memB <= _s.st.mem/2);
            return;
        }
        // 再在待购买区找
        for(int i = 0; i < serverClusterWait.size(); i++) {
            auto &_server = serverClusterWait[i];
            int score = INT_MAX, node = -1;
			if(2*_server.coreA >= _VMware.core && 2*_server.memA >= _VMware.mem && 2*_server.coreB >= _VMware.core && 2*_server.memB >= _VMware.mem) {
				score = min(a*_server.coreA-_VMware.core+b*(_server.memA-_VMware.mem/2), a*_server.coreB-_VMware.core+b*(_server.memB-_VMware.mem/2));
				node = 2;
			}
			if(node != -1 && score < minScore) {
				minScore = score;
				idx = i;
				deployNode = node;
				// break;
			}
        }
        // 如果找到了
        if(idx != -1) {
            auto &_s = serverClusterWait[idx];
            chooseServer(_s, VMID, deployNode);
            serverRunWait[_s.id].push_back(VMID);
            assert(_s.coreA >= 0 && _s.coreB >= 0 && _s.memA >= 0 && _s.memB >= 0);
            assert(_s.coreA <= _s.st.core/2 && _s.coreB <= _s.st.core/2 && _s.memA <= _s.st.mem/2 && _s.memB <= _s.st.mem/2);
            return;
        }
    }
    else {
        for(int i = 0; i < serverCluster.size(); i++) {
			auto &_server = serverCluster[i];
			int score = INT_MAX, node = -1;
			if(_server.coreA >= _VMware.core && _server.memA >= _VMware.mem) {
				score = a*(_server.coreA-_VMware.core)+b*(_server.memA-_VMware.mem);
				node = 0;
			}
			if(_server.coreB >= _VMware.core && _server.memB >= _VMware.mem) {
				int tmp = a*(_server.coreB-_VMware.core)+b*(_server.memB-_VMware.mem);
				// if(tmp < score) {
				if((score == INT_MAX) || (score != INT_MAX && tmp > score)) {
					score = tmp;
					node = 1;
				}
			}
			if(node != -1 && score < minScore) {
				minScore = score;
				idx = i;
				deployNode = node;
				// break;
			}
		}
        // 如果找到了
        if(idx != -1) {
            auto &_s = serverCluster[idx];
            chooseServer(_s, VMID, deployNode);
            serverRun[_s.id].push_back(VMID);
            assert(_s.coreA >= 0 && _s.coreB >= 0 && _s.memA >= 0 && _s.memB >= 0);
            assert(_s.coreA <= _s.st.core/2 && _s.coreB <= _s.st.core/2 && _s.memA <= _s.st.mem/2 && _s.memB <= _s.st.mem/2);
            return;
        }
        for(int i = 0; i < serverClusterWait.size(); i++) {
			auto &_server = serverClusterWait[i];
			int score = INT_MAX, node = -1;
			if(_server.coreA >= _VMware.core && _server.memA >= _VMware.mem) {
				score = a*(_server.coreA-_VMware.core)+b*(_server.memA-_VMware.mem);
				node = 0;
			}
			if(_server.coreB >= _VMware.core && _server.memB >= _VMware.mem) {
				int tmp = a*(_server.coreB-_VMware.core)+b*(_server.memB-_VMware.mem);
				// if(tmp < score) {
				if((score == INT_MAX) || (score != INT_MAX && tmp > score)) {
					score = tmp;
					node = 1;
				}
			}
			if(node != -1 && score < minScore) {
				minScore = score;
				idx = i;
				deployNode = node;
				// break;
			}
		}
        // 如果找到了
        if(idx != -1) {
            auto &_s = serverClusterWait[idx];
            chooseServer(_s, VMID, deployNode);
            serverRunWait[_s.id].push_back(VMID);
            assert(_s.coreA >= 0 && _s.coreB >= 0 && _s.memA >= 0 && _s.memB >= 0);
            assert(_s.coreA <= _s.st.core/2 && _s.coreB <= _s.st.core/2 && _s.memA <= _s.st.mem/2 && _s.memB <= _s.st.mem/2);
            return;
        }
    }

    for(auto &st : orderedServer) {
        auto s = server(st, -1);
        // 如果服务器合适，选择该服务器
		int node = haveFreeSpace(s, _VMware);
        if(node != -1) {
			s.id = serverClusterWait.size();
			serverClusterWait.push_back(s);
			// 重新部署
			chooseServer(serverClusterWait.back(), VMID, node);
			serverRunWait.push_back(list<int>{VMID});
			assert(serverClusterWait.back().coreA >= 0 && serverClusterWait.back().coreB >= 0 && serverClusterWait.back().memA >= 0 && serverClusterWait.back().memB >= 0);
			return;
        }
    }
}

// 删除请求
void delVMware(int VMID) {
    int serverIdx = VMwareOnServer[VMID].first;
    serverRun[serverIdx].remove(VMID);
    // 释放对应的server上的资源占用情况
    auto &_server = serverCluster[serverIdx];

	if(VMwareOnServer[VMID].second == 2) {
        _server.coreA += VMwareCluster[VMID].core/2;
        _server.coreB += VMwareCluster[VMID].core/2;
        _server.memA += VMwareCluster[VMID].mem/2;
        _server.memB += VMwareCluster[VMID].mem/2;
    }
    else {
        if(VMwareOnServer[VMID].second == 0) {
            _server.coreA += VMwareCluster[VMID].core;
            _server.memA += VMwareCluster[VMID].mem;
        }
        else {
            _server.coreB += VMwareCluster[VMID].core;
            _server.memB += VMwareCluster[VMID].mem;
        }
    }

    VMwareOnServer.erase(VMID);
}

// 服务器合并，A+A
void serverMerge() {
	if(serverClusterWait.empty()) return;
    vector<server> temp; // 存服务器
    vector<list<int>> tempRun;	// 存服务器上的虚拟机
    // 第几个服务器
    int i = 0;
    while(i+1 < serverClusterWait.size()) {
        int coreA = serverClusterWait[i].st.core/2 - serverClusterWait[i].coreA + serverClusterWait[i+1].st.core/2 - serverClusterWait[i+1].coreA;
        int coreB = serverClusterWait[i].st.core/2 - serverClusterWait[i].coreB + serverClusterWait[i+1].st.core/2 - serverClusterWait[i+1].coreB;
        int memA = serverClusterWait[i].st.mem/2 - serverClusterWait[i].memA   + serverClusterWait[i+1].st.mem/2 - serverClusterWait[i+1].memA;
        int memB = serverClusterWait[i].st.mem/2 - serverClusterWait[i].memB   + serverClusterWait[i+1].st.mem/2 - serverClusterWait[i+1].memB;
        int price = serverClusterWait[i].st.price + serverClusterWait[i+1].st.price;
        int cost = serverClusterWait[i].st.cost + serverClusterWait[i+1].st.cost;
		
        int s;
        for(s = 0; s < orderedServer.size(); s++) {
            auto &st = orderedServer[s];
            // 如果存在性价比更高的大服务器
            if(st.price < price && st.cost < cost && st.core/2 >= coreA && st.core/2 >= coreB && st.mem/2 >= memA && st.mem/2 >= memB) {
                // 进行转移
                server _server = server(st, -1);
                _server.coreA -= coreA;
                _server.coreB -= coreB;
                _server.memA -= memA;
                _server.memB -= memB;
				assert(_server.coreA >= 0 && _server.coreB >= 0 && _server.memA >= 0 && _server.memB >= 0);
                temp.push_back(_server);
                list<int> lst = serverRunWait[i];
                for(auto &VMID : serverRunWait[i+1]) {
                    lst.push_back(VMID);
                }
                tempRun.push_back(lst);
                i += 2;
                break;
            }
        }
        if(s == orderedServer.size()) {
            // 找不到更好的，就将第i个转移到temp中
            temp.push_back(serverClusterWait[i]);
            tempRun.push_back(serverRunWait[i]);
            i++;
        }
    }
    if(i == serverClusterWait.size()-1) {
        // 找不到更好的，就将第i个转移到temp中
        temp.push_back(serverClusterWait[i]);
        tempRun.push_back(serverRunWait[i]);
    }
	
    // 重新部署，并更新信息
    for(int ii = 0; ii < temp.size(); ii++) {
        server &s = temp[ii];
        befSer2ID[day].push_back(make_pair(s.st.type, serverID));
        s.id = serverID;
        serverCluster.push_back(s);
        purchaseCost += s.st.price;
        serverRun.push_back(tempRun[ii]);
        // 更新虚拟机的部署信息
        for(auto &VMID : serverRun.back()) {
            VMwareOnServer[VMID].first = serverID;
        }
        assert(serverCluster[serverID].coreA >= 0 && serverCluster[serverID].coreB >= 0 && serverCluster[serverID].memA >= 0 && serverCluster[serverID].memB >= 0);
        serverID++;
    }
}

// 对请求按照占用资源大小降序排序
bool cmp4(pair<int, int> &p1, pair<int, int> &p2) {
	int vmid1 = p1.second;
	int vmid2 = p2.second;
	return VMwareCluster[vmid1].core+VMwareCluster[vmid1].mem > VMwareCluster[vmid2].core+VMwareCluster[vmid2].mem;
}

// 处理第day天的请求
void serverAllocation(int day) {
	serNumDay = serverID;
	vector<pair<int, int>> request;

	vector<pair<int, int>> request1;
	vector<pair<int, int>> request2;
	for(auto req : quest[day]) {
		if(req.first == 1) {
			request1.push_back(req);
		}
		else {
			request2.push_back(req);
		}
	}
	sort(request1.begin(), request1.end(), cmp4);
	

    serverClusterWait.clear();
    serverRunWait.clear();

    // 处理请求信息
	for(int i = 0; i < request1.size(); i++) {
		auto &req = request1[i];
        int VMID = req.second;
        createVMware(VMID, day);

        VMwareNum++;
    }
    // 进行服务器合并
    serverMerge();
	
    for(int i = 0; i < request2.size(); i++) {
		auto &req = request2[i];
        int VMID = req.second;
        delVMware(VMID);
        VMwareNum--;
    }

	// 保存部署信息
	for(int i = 0; i < quest[day].size(); i++) {
		auto &req = quest[day][i];
        // 如果是add
        if(req.first == 1) {
            int VMID = req.second;
            if(VMwareOnServer[VMID].second == 0) dayResult[day].push_back(inform("(", VMwareOnServer[VMID].first, ", A)\n"));
			else if(VMwareOnServer[VMID].second == 1) dayResult[day].push_back(inform("(", VMwareOnServer[VMID].first, ", B)\n"));
			else dayResult[day].push_back(inform("(", VMwareOnServer[VMID].first, ")\n"));
        }
    }
}

// 对每天购买的服务器按照型号进行排序，方便后面ID映射
bool mycmp(pair<string, int> &a, pair<string, int> &b) {
    return a.first < b.first;
}

// 服务器ID映射第i天
void mapping(int i) {
    // 记录起始数字
    if(befSer2ID[i].empty()) return;
    int st = befSer2ID[i][0].second;
    // 排序
    sort(befSer2ID[i].begin(), befSer2ID[i].end(), mycmp);
    // 映射
    for(int j = 0; j < befSer2ID[i].size(); j++) {
        auto &temp = befSer2ID[i][j];
        aftMapping[temp.second] = to_string(st);
        st++;
        // 按顺序统计出现次数，方便后面输出
        if(j == 0) {
            serDayNum[i].push_back(make_pair(befSer2ID[i][j].first, 1));
        } else {
            if(befSer2ID[i][j].first == serDayNum[i].back().first) {
                serDayNum[i].back().second++;
            } else {
                serDayNum[i].push_back(make_pair(befSer2ID[i][j].first, 1));
            }
        }
    }
}

// 组合输出第i天字符串
void splic(int i) {
    result.clear();
    // 先拼接购买信息
    int num = serDayNum[i].size();
    result.push_back("(purchase, " + to_string(num) + ")\n");
    if(num != 0) {
        for(int j = 0; j < num; j++) {
            result.push_back("(" + serDayNum[i][j].first + ", " + to_string(serDayNum[i][j].second) + ")\n");
        }
    }
    // 再拼接迁移信息
    if(migrateResult[i].size() == 0) result.push_back("(migration, 0)\n");
    else {
        result.push_back("(migration, " + to_string(migrateResult[i].size()) + ")\n");
        for(int j = 0; j < migrateResult[i].size(); j++) {
            auto &mig = migrateResult[i][j];
			string res;
            res += mig.st;
            res += aftMapping[mig.id];
            res += mig.ed;
			result.push_back(res);
        }
    }
    // 再拼接部署信息
    for(int j = 0; j < dayResult[i].size(); j++) {
        auto &info = dayResult[i][j];
		string res;
        res += info.st;
        res += aftMapping[info.id];
        res += info.ed;
		result.push_back(res);
    }
    // 输出
	for(auto &s : result) {
		cout << s;
	}
    // cout << result;
	fflush(stdout);
}

// 日耗
void serverCost() {
    for(int i = 0; i < serverID; i++) {
        if(serverRun[i].size()) {
            dailyCost += serverCluster[i].st.cost;
        }
    }
}

// 负载率比较函数
bool cmp5(server &s1, server &s2) {
	// double radio1 = pow(1.0*(s1.st.core-s1.coreA-s1.coreB)/s1.st.core, 2)+pow(1.0*(s1.st.mem-s1.memA-s1.memB)/s1.st.mem, 2);
	// double radio2 = pow(1.0*(s2.st.core-s2.coreA-s2.coreB)/s2.st.core, 2)+pow(1.0*(s2.st.mem-s2.memA-s2.memB)/s2.st.mem, 2);
	// double radio1 = 1.0*(s1.st.core-s1.coreA-s1.coreB + s1.st.mem-s1.memA-s1.memB)/(s1.st.core + s1.st.mem);
	// double radio2 = 1.0*(s2.st.core-s2.coreA-s2.coreB + s2.st.mem-s2.memA-s1.memB)/(s2.st.core + s2.st.mem);
	double radio1 = 1.0*(s1.st.core-s1.coreA-s1.coreB)/s1.st.core + 1.0*(s1.st.mem-s1.memA-s1.memB)/s1.st.mem;
	double radio2 = 1.0*(s2.st.core-s2.coreA-s2.coreB)/s2.st.core + 1.0*(s2.st.mem-s2.memA-s2.memB)/s2.st.mem;
	
	return radio1 < radio2;
}

// 按照服务器上的虚拟机个数比较
bool ccmp5(server &s1, server &s2) {
	return serverRun[s1.id].size() < serverRun[s2.id].size();
}

// 迁移
void migration(int day) {
	
	int times;
	if(addDelTimes[day-1][1] > 1000 && D == 1) {
		times = VMwareNum;
		D = 0;
	}
	else {
		times = 3*VMwareNum/100;
	}
	if(times == 0) return;

	double target = 1.0;
	int p = 6;
	while(p > 0) {
		p--;
		target -= 0.002;

		vmwareVec.clear();
		vmwareOnVec.clear();
		
		vector<server> tmp;
		
		for(int i = 0; i < serverID; i++) {
			auto &_server = serverCluster[i];
			double radio = (1.0*(_server.st.core-_server.coreA-_server.coreB)/_server.st.core + 1.0*(_server.st.mem-_server.memA-_server.memB)/_server.st.mem)/2;
			if(radio > target) {
				continue;
			}
			else if(serverRun[i].size() > 0) tmp.push_back(_server);
		}
		
		sort(tmp.begin(), tmp.end(), ccmp5);
		// 记录迁移不动的虚拟机类型
		unordered_map<string, bool> book;
		for(int i = 0; i < tmp.size(); i++) {
			int id = tmp[i].id;
			auto &_server = serverCluster[id];

			int n = 2;
			for(auto VMID : serverRun[id]) {
				if(deleteDay[VMID] == day) continue;
				vmwareVec.push_back(VMID);
				book[VMwareIDtoStr[VMID]] = false;
				vmwareOnVec[VMID] = VMwareOnServer[VMID];
				n--;
				if(n <= 0) break;
			}
		}

		for(int i = 0; i < vmwareVec.size() ; i++) {
			int VMID = vmwareVec[i];
			// 如果之前迁移不动，就continue
			if(book[VMwareIDtoStr[VMID]] == true) continue;
			VMware &_VMware = VMwareCluster[VMID];
			// 原来处于的服务器ID
			int serID = vmwareOnVec[VMID].first;
			auto &_server = serverCluster[serID];
			// 原来的服务器的负载率
			double initRadio = (1.0*(_server.st.core-_server.coreA-_server.coreB)/_server.st.core + 1.0*(_server.st.mem-_server.memA-_server.memB)/_server.st.mem)/2;
			if(initRadio > target) continue;
			
			delVMware(VMID);
			
			int idx = -1, deployNode = -1;
			int minScore = INT_MAX;
			
			if(_VMware.binode == 1) {
				for(int i = 0; i < serverID; i++) {
					int id = i;
					auto &_server = serverCluster[id];
					int score = INT_MAX, node = -1;
					if(2*_server.coreA >= _VMware.core && 2*_server.memA >= _VMware.mem && 2*_server.coreB >= _VMware.core && 2*_server.memB >= _VMware.mem) {
						score = min(a*_server.coreA-_VMware.core+b*(_server.memA-_VMware.mem/2), a*_server.coreB-_VMware.core+b*(_server.memB- _VMware.mem/2));
						node = 2;
					}
					if(node != -1 && score < minScore) {
						minScore = score;
						idx = id;
						deployNode = node;
					}
				}
			} else {
				for(int i = 0; i < serverID; i++) {
					int id = i;
					auto &_server = serverCluster[id];
					int score = INT_MAX, node = -1;
					if(_server.coreA >= _VMware.core && _server.memA >= _VMware.mem) {
						score = a*(_server.coreA-_VMware.core)+b*(_server.memA-_VMware.mem);
						node = 0;
					}
					if(_server.coreB >= _VMware.core && _server.memB >= _VMware.mem) {
						int tmp = a*(_server.coreB-_VMware.core)+b*(_server.memB-_VMware.mem);
						// if(tmp < score) {
						if((score == INT_MAX) || (score != INT_MAX && tmp > score)) {
							score = tmp;
							node = 1;
						}
					}
					if(node != -1 && score < minScore) {
						minScore = score;
						idx = id;
						deployNode = node;
					}
				}
			}
			
			if(idx != -1) {
				if(idx != serID && serverRun[idx].empty()) {
					idx = serID;
					deployNode = vmwareOnVec[VMID].second;
				}
				auto &_s = serverCluster[idx];
				chooseServer(_s, VMID, deployNode);
				serverRun[_s.id].push_back(VMID);
				if(vmwareOnVec[VMID] == VMwareOnServer[VMID]) {
					book[VMwareIDtoStr[VMID]] = true;
				}
				if(vmwareOnVec[VMID] != VMwareOnServer[VMID]) {
					if(deployNode == 0) {
						migrateResult[day].push_back(inform("("+to_string(VMID)+", ", _s.id, ", A)\n"));
					} else if(deployNode == 1) {
						migrateResult[day].push_back(inform("("+to_string(VMID)+", ", _s.id, ", B)\n"));
					} else {
						migrateResult[day].push_back(inform("("+to_string(VMID)+", ", _s.id, ")\n"));
					}
					times--;
				} else {
					number++;
				}
			}
			if(times <= 0) return;
		}
		if(times <= 0) return;
	}
}

void processing() {
    // 迁移
	if(day != 0) migration(day);
	
    // 处理请求
    serverAllocation(day);
    // 日耗
    serverCost();
    // ID映射
    mapping(day);
    // 输出
    splic(day);

    day++;
}


int main(int argc, char* argv[]) {
    // string s(argv[1]);
	// string filePath = "./data/training-" + s + ".txt";
    // freopen(filePath.c_str(),"rb",stdin);

    readInfo();
    sortServer();
    for(int t = 0; t < days; t++) {
        if(t == 50*days/100+1) {
            sort(orderedServer.begin(), orderedServer.end(), ccmp1);
        }
        string opera, VMtype, VMID;
        vector<pair<int, int>> questTemp;
        int n;  // 每天n个请求
        cin >> n;
        for(int i = 0; i < n; i++) {
            // 先读取请求类型
            cin >> opera;
            // 格式化后的请求类型， 虚拟机型号，虚拟机ID
            string _opera, _VMtype, _VMID;
            // 如果是添加请求
            if(opera[1] == 'a') {
                cin >> VMtype >> VMID;
                _opera = opera.substr(1, opera.size() - 2);
                _VMtype = VMtype.substr(0, VMtype.size() - 1);
                _VMID = VMID.substr(0, VMID.size() - 1);
                VMwareCluster[stoi(_VMID)] = VMwareTable[_VMtype];
				VMwareIDtoStr[stoi(_VMID)] = _VMtype;
                addDelTimes[t][0]++; // 添加次数
            }
            // 如果是删除请求，表明删除已有虚拟机
            else {
                cin >> VMID;
                _opera = opera.substr(1, opera.size() - 2);
                _VMID = VMID.substr(0, VMID.size() - 1);
                addDelTimes[t][1]++; // 删除次数
                deleteDay[stoi(_VMID)] = t;
            }
            // 记录下此时的请求类型和ID
            if(_opera == "add") questTemp.push_back(make_pair(1, stoi(_VMID)));
			else questTemp.push_back(make_pair(0, stoi(_VMID)));
        }
        // 将当天请求保存下来
		quest.push_back(questTemp);
        processing();
    }
#ifdef TEST
	int migTime = 0;
	for(int i = 0; i < days; i++) {
		migTime += migrateResult[i].size();
	}
	totalCost = purchaseCost + dailyCost;
	cout << "server num = " << serverID << endl;
	cout << "migration times: " << migTime << endl;
    cout << "total cost: " << totalCost << ", purchase cost: " << purchaseCost << ", daily cost: " << dailyCost << endl;
	cout << "invalid migration: " << number << endl;

#endif

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/一键难忘520/article/detail/919117