CTF of Z2BNS
0%

2021华为软件精英挑战赛

发表于 更新于 分类于
| 阅读次数： |
Valine：
本文字数： 1.2k 阅读时长 ≈ 1 分钟

【比赛地址】

【初赛赛题说明、技术Q&A、练习赛数据集、SDK】

比赛简介

服务器

服务器类型

每台服务器存在A和B两个节点。

参数：

CPU核数、内存大小、硬件成本、能耗成本（没有部署虚拟机时没有能耗）

虚拟机

虚拟机类型

单节点/双节点部署

资源规划和调度
请求类型

创建虚拟机和删除虚拟机

请求序列

由一系列请求构成的序列，根据每天请求序列进行资源规划与调度

数据中心扩容

根据请求序列购买新的服务器，购买的每台服务器从0开始递增编号，总量不超过$10^5$

虚拟机迁移

完成扩容，处理每一天的新请求之前把虚拟机从一台服务器迁移到另一台服务器，不超过虚拟机总量的千分之5

部署虚拟机

指定部署在服务器的A节点或B节点

输入示例说明
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
//一个整数N(1<=N<=100)：可采购服务器类型数量
2
//N行，每行描述一种类型的服务器(型号, CPU 核数, 内存大小, 硬件成本, 每日能耗成本)。
(NV603, 92, 324, 53800, 500)
(NV604, 128, 512, 87800, 800)
//一个整数M(1<=M<=1000):售卖的虚拟机类型数量
2
//M行，每行描述一种类型虚拟机：(型号, CPU 核数, 内存大小, 是否双节点部署)，0表示单节点。
(c3.large.4, 2, 8, 0)
(c3.8xlarge.2, 32, 64, 1)
//一个整数T(1<=T<=1000)，T天
3
//T组数据
//第一天，一个整数R(R>=0):R条请求
2
//R行请求数据(add, 虚拟机型号, 虚拟机 ID)或(del, 虚拟机 ID)
(add, c3.large.4, 5)
(add, c3.large.4, 0)
2
(del, 0)
(add, c3.8xlarge.2, 1)
//第T天
3
(add, c3.large.4, 2)
(del, 1)
(del, 2)
输出示例说明

对于每 一天的操作，会先按顺序执行选手输出的购买操作，然后按顺序执行选手输出的迁移操作，最后 按顺序执行当天的创建和删除操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//输出按顺序包含T天中每一天的决策信息
//(purchase,Q),Q是购买服务器的类型数量(0<=Q<=N)
(purchase, 2)
//Q行，每行(服务器型号，购买数量)
(NV603, 1)
(NV604, 1)
//(migration,W),W为迁移虚拟机的数量
(migration, 0)
//W行，表示虚拟机迁移(虚拟机ID，目的服务器ID，(目的服务器节点--双节点部署则省略))
//对当天每个创建请求部署服务器，(服务器ID，(部署节点--双节点省略))
(0, A)
(0, B)
//下一天
(purchase, 0)
(migration, 0)
(1)
//第T天
(purchase, 0)
(migration, 0)
(1, B)

解题过程

这两天稍微看了看，感觉就是一道复杂的ACM题，写了一点基础的代码，也没更多的时间去看了，我得去看论文了，先记录一下，以后有时间也许会研究一下。

思路

先不考虑总成本，先写完程序满足请求序列

难点

怎么衡量每台服务器的性价比？

怎么选购服务器？

代码

c++基础版代码（未考虑硬件成本）

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
#include<unordered_map>
#include "iostream"
#include<string>
#include<vector>
#include<fstream>
using namespace std;

int main() {
    // TODO:read standard input
    // TODO:process
    // TODO:write standard output
    // TODO:fflush(stdout);
    //以读模式打开文件
    //ifstream file;
    //测试数据
    //infile.open("./1.txt");
    //infile.open("./training-1.txt");
    int i = 0, j = 0, k = 0;
    //N可采购服务器类型数量
    int N;
    cin >> N;
    unordered_map<string, vector<int>> server_type_list;
    string s;
    vector<int> arr;
    vector<string> server_random;
    //(NV603, 92, 324, 53800, 500)
    string key;
    for(i = 0; i < N; i++) {
        cin >> s;
        //对每种服务器类型数据进行解析
        //获取服务器型号
        key = s.substr(1, s.length() - 2);
        server_random.emplace_back(key);
        cin >> s;
        s = s.substr(0, s.length() - 1);
        //cpu核数
        arr.emplace_back(atoi(s.c_str()));
        cin >> s;
        s = s.substr(0, s.length() - 1);
        //内存大小
        arr.emplace_back(atoi(s.c_str()));
        cin >> s;
        s = s.substr(0, s.length() - 1);
        //硬件成本
        arr.emplace_back(atoi(s.c_str()));
        cin >> s;
        s = s.substr(0, s.length() - 1);
        //每日能耗成本
        arr.emplace_back(atoi(s.c_str()));
        server_type_list[key] = arr;
        arr.clear();
    }
    //cout<<server_type_list.size()<<endl;
    //售卖的虚拟机类型数量
    int M;
    unordered_map<string, vector<int>> vm_type_list;
    cin >> M;
    for(i = 0; i < M; i++) {
        cin >> s;
        //对每种虚拟机类型数据进行解析
        //获取虚拟机型号
        key = s.substr(1, s.length() - 2);
        cin >> s;
        s = s.substr(0, s.length() - 1);
        //cpu核数
        arr.emplace_back(atoi(s.c_str()));
        cin >> s;
        s = s.substr(0, s.length() - 1);
        //内存大小
        arr.emplace_back(atoi(s.c_str()));
        cin >> s;
        //是否双节点部署
        s = s.substr(0, s.length() - 1);
        arr.emplace_back(atoi(s.c_str()));
        vm_type_list[key] = arr;
        arr.clear();
    }
    //cout<<vm_type_list.size()<<endl;
    //T天
    int T;
    cin >> T;
    //每天R条请求
    int R;
    //操作命令
    string op;
    int core_demand = 0;
    int memory_demand = 0;
    string vm_type;
    int vm_core = 0;
    int vm_memory = 0;
    int vm_id;
    //服务器空闲资源（key=服务器id,value=(A节点空闲核数，A节点内存，B核数，内存)）
    vector<vector<int>> free_server_list;
    //要购买的服务器
    vector<int> purchase_server;
    int free_memory = 0;
    int server_random_num;
    //int purchase_server_type=0;
    //是否双节点部署
    int deploy_type = 0;
    vector<int> vm;
    bool fail_deploy = true;
    unordered_map<string, int> purchase_server_list;
    //部署服务器列表(服务器id，部署节点（双节点省略）)
    vector<string> deploy_server_list;
    string deploy_server = "";
    //虚拟机ID与服务器编号和节点的映射(0/1/2--A/B/双,服务器编号,虚拟机核数，虚拟机内存)
    unordered_map<int, vector<int>> vm_server_map;
    vector<int> server_num;
    //购买服务器的类型数量
    int Q = 0;
    for(i = 0; i < T; i++) {
        //处理每一天的请求序列
        cin >> R;
        //先统计总共需要多少资源，然后输出购买信息
        //每天购买服务器类型初始为0
        //purchase_server_type=0;
        for(k = 0; k < R; k++) {
            core_demand = 0;
            memory_demand = 0;
            cin >> op;
            op = op.substr(1, op.length() - 2);
            if(op == "add") {
                deploy_server = "(";
                //读取请求创建的虚拟机型号
                cin >> s;
                vm_type = s.substr(0, s.length() - 1);
                vm = vm_type_list[vm_type];
                //cout<<vm[0]<<" "<<vm[1]<<endl;
                core_demand += vm[0];
                memory_demand += vm[1];
                //是否双节点部署
                deploy_type = vm[2];
                //虚拟机ID
                cin >> s;
                vm_id = atoi(s.substr(0, s.length() - 1).c_str());
                fail_deploy = true;
                while(fail_deploy) {
                    if(deploy_type == 0) {
                        for(j = 0; j < free_server_list.size(); j++) {
                            //cout<<"j="<<j<<endl;
                            //cout<<"free_server_list[j][0]_core:"<<free_server_list[j][0]<<endl;
                            if(free_server_list[j][0] >= core_demand && free_server_list[j][1] >= memory_demand) {
                                //部署到编号为j的服务器的A节点上
                                free_server_list[j][0] -= core_demand;
                                free_server_list[j][1] -= memory_demand;
                                server_num.emplace_back(0);
                                //j转string
                                deploy_server += to_string(j) + ", A)";
                                fail_deploy = false;
                                break;

                            } else if(free_server_list[j][2] >= core_demand && free_server_list[j][3] >= memory_demand) {
                                //部署到编号为j的服务器的B节点上
                                free_server_list[j][2] -= core_demand;
                                free_server_list[j][3] -= memory_demand;
                                server_num.emplace_back(1);
                                deploy_server += to_string(j) + ", B)";
                                fail_deploy = false;
                                break;
                            }
                        }
                        if(j == free_server_list.size() || free_server_list.size() == 0) {
                            //部署失败需要购买服务器
                            fail_deploy = true;
                        } else {
                            //部署虚拟机时做好与服务器的映射
                            server_num.emplace_back(j);
                            server_num.emplace_back(core_demand);
                            server_num.emplace_back(memory_demand);
                            vm_server_map[vm_id] = server_num;
                            server_num.clear();
                            deploy_server_list.emplace_back(deploy_server);
                        }
                    } else {
                        //双节点部署
                        for(j = 0; j < free_server_list.size(); j++) {
                            if(free_server_list[j][0] >= core_demand / 2 && free_server_list[j][1] >= memory_demand / 2 && free_server_list[j][2] >= core_demand / 2 && free_server_list[j][3] >= memory_demand / 2) {
                                //部署到编号为j的服务器的A节点上
                                free_server_list[j][0] -= core_demand / 2;
                                free_server_list[j][1] -= memory_demand / 2;
                                free_server_list[j][2] -= core_demand / 2;
                                free_server_list[j][3] -= memory_demand / 2;
                                fail_deploy = false;
                                server_num.emplace_back(2);
                                break;
                            }
                        }
                        if(j == free_server_list.size() || free_server_list.size() == 0) {
                            //部署失败需要购买服务器
                            fail_deploy = true;
                        } else {
                            deploy_server += to_string(j) + ")";
                            server_num.emplace_back(j);
                            server_num.emplace_back(core_demand);
                            server_num.emplace_back(memory_demand);
                            vm_server_map[vm_id] = server_num;
                            server_num.clear();
                            deploy_server_list.emplace_back(deploy_server);
                        }
                    }
                    if(fail_deploy) {
                        //随机购买一台服务器
                        server_random_num = rand() % server_random.size();
                        //cout<<"purchase server type:"<<server_random[server_random_num]<<endl;
                        purchase_server.emplace_back(server_type_list[server_random[server_random_num]][0] / 2);
                        purchase_server.emplace_back(server_type_list[server_random[server_random_num]][1] / 2);
                        purchase_server.emplace_back(server_type_list[server_random[server_random_num]][0] / 2);
                        purchase_server.emplace_back(server_type_list[server_random[server_random_num]][1] / 2);

                        //cout<<"core_A:"<<server_type_list[server_random[server_random_num]][0]/2<<endl;
                        //cout<<"memory_A:"<<server_type_list[server_random[server_random_num]][1]/2<<endl;
                        //将购买的这台服务器放到空闲服务器列表中
                        free_server_list.emplace_back(purchase_server);
                        //purchase_server每次要清空，不然一直买服务器直到程序卡死
                        purchase_server.clear();
                        //对应的购买服务器型号数量加1
                        purchase_server_list[server_random[server_random_num]]++;
                    }
                }
            } else {
                //删除虚拟机请求
                //获取要删除的虚拟机id
                cin >> s;
                //substr(1,strlength()-2),原来写的是1和2，通过debug改正了这个bug
                vm_id = atoi(s.substr(0, s.length() - 1).c_str());
                //根据部署映射获取虚拟机部署所依托的服务器编号和节点
                //然后把删除虚拟机的资源加到空闲服务器资源中
                if(vm_server_map[vm_id][0] == 0) {
                    free_server_list[vm_server_map[vm_id][1]][0] += vm_server_map[vm_id][2];
                    free_server_list[vm_server_map[vm_id][1]][1] += vm_server_map[vm_id][3];
                } else if(vm_server_map[vm_id][0] == 1) {
                    free_server_list[vm_server_map[vm_id][1]][2] += vm_server_map[vm_id][2];
                    free_server_list[vm_server_map[vm_id][1]][3] += vm_server_map[vm_id][3];
                } else {
                    free_server_list[vm_server_map[vm_id][1]][0] += vm_server_map[vm_id][2] / 2;
                    free_server_list[vm_server_map[vm_id][1]][1] += vm_server_map[vm_id][3] / 2;
                    free_server_list[vm_server_map[vm_id][1]][2] += vm_server_map[vm_id][2] / 2;
                    free_server_list[vm_server_map[vm_id][1]][3] += vm_server_map[vm_id][3] / 2;
                }
            }
        }
        //输出每天的决策信息
        //输出购买服务器的类型数量Q
        Q = purchase_server_list.size();
        //cout<<"**************************THE "<<i<<" DAY**************************"<<endl;
        cout << "(purchase, " << Q << ")" << endl;
        //遍历购买的服务器类型和数量
        unordered_map<string, int>::iterator iter;
        for(iter = purchase_server_list.begin(); iter != purchase_server_list.end(); iter++) {
            cout << "(" << iter->first << ", " << iter->second << ")" << endl;
        }
        //输出迁移虚拟机信息
        cout << "(migration, 0)" << endl;
        //cout<<部署虚拟机信息
        for(j = 0; j < deploy_server_list.size(); j++) {
            cout << deploy_server_list[j] << endl;
        }
        //存储每天决策信息容器清空
        purchase_server_list.clear();
        deploy_server_list.clear();
    }
    return 0;
}
运行结果

设计比较简短的测试文件test_input.txt输入文件，test.input.txt内容如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
(NV603, 92, 324, 53800, 500)
(NV604, 128, 512, 87800, 800)
2
(c3.large.4, 2, 8, 0)
(c3.8xlarge.2, 32, 64, 1)
3
2
(add, c3.large.4, 5)
(add, c3.large.4, 0)
2
(del, 0)
(add, c3.8xlarge.2, 1)
3
(add, c3.large.4, 2)
(del, 1)
(del, 2)

运行结果如下：

image-20210319165408571

使用training-1.txt测试结果如下：

image-20210319205322878

使用training-2.txt测试结果如下：

image-20210319205426421

提交结果
提交v1.0

image-20210319213325724

根据要求提交压缩文件后，运行提示”选手程序运行错误-运行程序异常退出“，文档说明里说可能是内存超出4G，不能吧🤨。

image-20210319213806672

然后排查一遍，发现应该是输入数据方式不对，应该是标准输入，我是用的文件输入。

image-20210319213912903

那应该就是输入背锅了，读取不到数据导致程序异常退出。啊啊啊啊，还要改输入，行吧改吧，期待改过之后的提交结果。

提交v2.0

其实把文件输入修改成标准输入只需要注释掉下面三行代码然后把其他的infile>>改成cin>>就行了。

#include<fstream>

......

ifstream file;

infile.open("./1.txt");

提交后提示错误

image-20210320083753583

然后去过一遍代码排查一下，果然发现了问题

image-20210320091446632

第一处错误

if判断条件关系运算符写成了赋值运算符，导致删除双节点部署虚拟机后资源分配按照部署到B节点进行计算，造成B节点核数和内存偏大，分配虚拟机时造成了放置虚拟机超出服务器资源限制（CPU或内存）。

第二处错误

del操作：索引写错了，导致删除双节点部署的虚拟机时，B节点释放的内存大小加到了B节点释放的核数上面，造成空闲的B节点核数偏大。

改完这两处依然报这个错误，排查了几遍没有错误啊，啊啊啊啊啊，没有错误啊，为啥就是分配虚拟机超出资源限制呢，奇怪？？？

总结

代码缺少高效的算法，采用了每次随机购买服务的方法，应该进一步研究去寻求更低的硬件成本，有时间再去想想怎么优化吧。

------------- THE END! THANKS! -------------