抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

第一次参加这种比赛,到最后也没有分数,很难受,明年再战吧。

感觉思路并不是妹有道理的QAQ

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

static string CONFIG_PATH = "/data/config.ini";
static string DATA_PATH = "/data/";
static string OUTPUT_PATH = "/output/solution.txt";
const static int MAX_CLIENT = 36; // 最大的客户节点
const static int MAX_SITE = 136; //最大的边缘节点
int clientArrLen;
int siteArrLen;
int QOS_LIMIT; // 最大延迟


// 主需要获取每个时间点所有的需求序列及其通过索引能够确定相应的客户节点的名字即可。
vector<string> timeSeqName;//时间序列的名字
vector<vector<int> > demand;//每个时间节点的贷款需求序列

/**
* Site,即任务书中的边缘节点
*/
struct SiteNode
{
string siteName;
int siteIndex;
int bandwidth; //该Site可分配的最大上限,不超过1000000MB
int curAlloc; //当前该节点分配到流量。
bool ifAllocSat(int cnt) // 是否满足分配cnt流量
{
return curAlloc + cnt <= bandwidth;
}
int hot = 0; //热度
int timeT = 0; //高占用时间
int Origin = 0;
} siteArr[MAX_SITE];
/**
*
* 客户节点
*/
struct ClientNode
{
string clientName;
vector<vector<pair<int, int>>> alloc; //每个时间点site节点分配的索引及流量
} clientArr[MAX_CLIENT];

struct QosTable
{
// 初始化每个连接关系都为最大值
int qosData[MAX_SITE][MAX_CLIENT];
inline bool ifQosSat(int siteIndex, int clientIndex)
{
return qosData[siteIndex][clientIndex] < QOS_LIMIT;
}
} qosTable;



/**
* String split by delimiters
*/
static vector<string> split(const string& s, const string& delimiters = ",")
{
vector<string> tokens;
size_t lastPos = s.find_first_not_of(delimiters, 0);
size_t pos = s.find_first_of(delimiters, lastPos);
while (pos != string::npos || lastPos != string::npos)
{
tokens.emplace_back(s.substr(lastPos, pos - lastPos));
lastPos = s.find_first_not_of(delimiters, pos);
pos = s.find_first_of(delimiters, lastPos);
}
return tokens;
}
/**
* 返回一行的数字vector
*/
static vector<int> split2(const string& s, const string& delimiters = ",")
{
string str;
vector<int> tokens;
size_t lastPos = s.find_first_not_of(delimiters, 0);//查找第一个非,
size_t pos = s.find_first_of(delimiters, lastPos);//查找第一个,
str = s.substr(lastPos, pos - lastPos);
lastPos = s.find_first_not_of(delimiters, pos);
pos = s.find_first_of(delimiters, lastPos);
while (pos != string::npos || lastPos != string::npos)
{
tokens.emplace_back(atoi(s.substr(lastPos, pos - lastPos).c_str()));
lastPos = s.find_first_not_of(delimiters, pos);
pos = s.find_first_of(delimiters, lastPos);
}
return tokens;
}

/**
* read Config
*/
void readConf()
{
ifstream config;
config.open(CONFIG_PATH);
string tmp_line;
getline(config, tmp_line);
getline(config, tmp_line);
QOS_LIMIT = atoi(string(tmp_line.begin() + tmp_line.find('=') + 1, tmp_line.end()).c_str());
config.close();
}
/**
* read site_bandwidth.csv, qos.csv, demand.csv
*/
void readData()
{
vector<string> tmp_vec;
vector<int> tmp_vec2;
ifstream data;
string tmp_line;
unsigned int index = 0;
//初始化边缘节点列表以及每个边缘节点的带宽上限
data.open(DATA_PATH + "demand.csv");
string client_temp;
getline(data, client_temp);
data.close();
data.clear();
data.open(DATA_PATH + "site_bandwidth.csv");
getline(data, tmp_line);
// cout << tmp_line << endl;
while (getline(data, tmp_line))
{
tmp_vec = split(tmp_line, ",");
siteArr[index].siteName = tmp_vec[0];
siteArr[index].bandwidth = atoi(tmp_vec[1].c_str());
siteArr[index].curAlloc = 0;
siteArr[index].siteIndex = index;
index++;
}
siteArrLen = index;
data.close();
data.clear();

//客户节点和边缘节点的Qos
string tmp_name;
data.open(DATA_PATH + "qos.csv");
getline(data, tmp_name);
// cout << tmp_line << endl;
tmp_vec = split(client_temp, ",");
for (index = 0; index < tmp_vec.size() - 1; index++)
{
clientArr[index].clientName = tmp_vec[static_cast<std:: vector<std::string, std::allocator<std::string>>::size_type>(index)+1];
}
clientArrLen = index;
while (clientArr[clientArrLen - 1].clientName[clientArr[clientArrLen - 1].clientName.length() - 1] == '\r')
clientArr[clientArrLen - 1].clientName.erase(clientArr[clientArrLen - 1].clientName.end() - 1);

// 处理每个节点的Qos
while (getline(data, tmp_line))
{
string sitename_temp = tmp_line.substr(0, tmp_line.find(','));
for (int i = 0; i < siteArrLen; i++) {
if (siteArr[i].siteName == sitename_temp) {
index = i;
break;
}
}
tmp_vec2 = split2(tmp_line, ",");
string tttmp;
if (tmp_name[tmp_name.length()] == '\r')
tttmp = tmp_name.substr(0, tmp_name.length() - 1);
else
tttmp = tmp_name;
auto xxvec = split(tttmp, ",");
int k = 0, sum = 0;
while (sum != clientArrLen)
{
for (int i = 0; i < clientArrLen; i++)
{
if (clientArr[i].clientName == xxvec[sum + 1])
{
k = i;
break;
}
}
qosTable.qosData[index][k] = tmp_vec2[sum];
sum++;
}
}
data.close();
data.clear();

//客户节点在不同时刻的带宽需求信息
data.open(DATA_PATH + "demand.csv");
getline(data, tmp_line);
index = 0;
while (getline(data, tmp_line))
{
timeSeqName.push_back(tmp_line.substr(0, tmp_line.find_first_of(",")));
demand.push_back(split2(tmp_line, ","));
}
data.close();
data.clear();
}

bool cmpHot(const SiteNode& a, const SiteNode& b)
{
return a.hot > b.hot;
} //按热度排序

void allocateBandwith(int timeIndex, ostream& fout) //最简化版,暂未考虑溢出,热度与95%的阻止
{
for (int i = 0; i < siteArrLen; i++)
{
siteArr[i].curAlloc = 0;
siteArr[i].Origin = 0;
}

for (int i = 0; i < clientArrLen; ++i)//主要逻辑
{
//TODO:写入客户名字
fout << clientArr[i].clientName << ':';
if (demand[timeIndex][i] == 0)
{
fout << '\n';
continue;
}
vector<int> avIndex;
for (int j = 0; j < siteArrLen; ++j)
{
if (qosTable.ifQosSat(siteArr[j].siteIndex, i))
{
if (siteArr[j].timeT < 0.05 * siteArrLen-1)
{
avIndex.push_back(j);
}
}

}
//main
string temp;
int shengYu = 0;
int tempD = demand[timeIndex][i] / (avIndex.size());
vector<int> alloc(siteArrLen);
for (auto j : avIndex)
{
siteArr[j].Origin = siteArr[j].curAlloc;
}
for (auto j : avIndex) //计算总可分配流量
{
if (siteArr[j].timeT >= timeSeqName.size() * 0.05 - 1)
{
continue;
}
//计算alloc
siteArr[j].curAlloc += tempD;
if (j == *(avIndex.end() - 1))//最后一个节点要把所有的带宽都补上
{
siteArr[j].curAlloc -= tempD;
siteArr[j].curAlloc += demand[timeIndex][i] - (avIndex.size() - 1) * tempD;
}
siteArr[j].curAlloc += shengYu;
if (siteArr[j].curAlloc > siteArr[j].bandwidth)//如果超出限额了,就给下一个节点
{
shengYu = siteArr[j].curAlloc - siteArr[j].bandwidth;
siteArr[j].curAlloc = siteArr[j].bandwidth;
if (j == *(avIndex.end() - 1))//如果该节点为最后一个节点,则开启新一轮循环
{
for (auto k : avIndex)
{
siteArr[k].curAlloc += shengYu;
if (siteArr[k].curAlloc > siteArr[k].bandwidth)
{
shengYu = siteArr[k].curAlloc - siteArr[k].bandwidth;
siteArr[k].curAlloc = siteArr[k].bandwidth;
alloc[k] = siteArr[k].curAlloc - siteArr[k].Origin;//TODO:写入带宽
}
else
{
alloc[k] = siteArr[k].curAlloc - siteArr[k].Origin;
break;
}
}
}
}
else
{
shengYu = 0;
}
alloc[j] = siteArr[j].curAlloc - siteArr[j].Origin;//TODO:写入带宽
}
for (auto j : avIndex)//输出alloc
{
if (alloc[j] != 0)
temp += "<" + siteArr[j].siteName + "," + to_string(alloc[j]) + ">,";
}
if (temp != "")
temp.erase(temp.end() - 1);
temp += '\n';
fout << temp;
shengYu = 0;
}
for (int i = 0; i < siteArrLen; i++)
{
if (siteArr[i].curAlloc > siteArr[i].bandwidth * 0.95)//如果超出0.95,高占用++
{
siteArr[i].timeT++;
}
}
}

void allocateBandwith2(int timeIndex, ostream& fout) //剩余5%的时间
{
for (int i = 0; i < siteArrLen; i++)
{
siteArr[i].curAlloc = 0;
siteArr[i].Origin = 0;
}
for (int i = 0; i < clientArrLen; i++)//主要逻辑
{
//TODO:写入客户名字
fout << clientArr[i].clientName << ':';
if (demand[timeIndex][i] == 0)
{
fout << '\n';
continue;
}
vector<int> avIndex;//寻找延迟符合条件的节点
for (int j = 0; j < siteArrLen; ++j)
{
if (qosTable.ifQosSat(siteArr[j].siteIndex, i))
{
avIndex.push_back(j);
}

}
int shengYu = 0;
string temp;
for (auto j : avIndex)
{
siteArr[j].Origin = siteArr[j].curAlloc;
}
int flag2 = 0;
for (auto j : avIndex) //计算总可分配流量
{
if (siteArr[j].timeT >= timeSeqName.size() * 0.05 - 1)
{
continue;
}
//TODO:写入边缘节点名字
if (flag2 == 0)
{
siteArr[j].curAlloc += demand[timeIndex][i];
}
siteArr[j].curAlloc += shengYu;
if (siteArr[j].curAlloc > siteArr[j].bandwidth)//如果超出限额了,就给下一个节点,同时高占用++
{
shengYu = siteArr[j].curAlloc - siteArr[j].bandwidth;
siteArr[j].curAlloc = siteArr[j].bandwidth;
flag2 = 1;
if (siteArr[j].curAlloc == siteArr[j].Origin)
continue;
int alloc = siteArr[j].curAlloc - siteArr[j].Origin;//TODO:写入带宽
temp += "<" + siteArr[j].siteName + "," + to_string(alloc) + ">,";
continue;
}
if (siteArr[j].curAlloc == siteArr[j].Origin)
break;
int alloc = siteArr[j].curAlloc - siteArr[j].Origin;//TODO:写入带宽
temp += "<" + siteArr[j].siteName + "," + to_string(alloc) + ">,";
break;
}
if (temp != "")
temp.erase(temp.end() - 1);
temp += '\n';
fout << temp;
shengYu = 0;
}
for (int i = 0; i < siteArrLen; i++)
{
if (siteArr[i].curAlloc > siteArr[i].bandwidth * 0.95)//如果超出0.95,高占用++
{
siteArr[i].timeT++;
}
}
}


void testIO()
{
readConf();
readData();
}

int main()
{
ofstream output(OUTPUT_PATH, ios::out);
testIO();
for (int j = 0; j < siteArrLen; ++j) //获得热度
{
for (int i = 0; i < clientArrLen; ++i)
{
if (qosTable.ifQosSat(siteArr[j].siteIndex, i))
{
siteArr[j].hot++;
}
}
}
sort(siteArr, siteArr + siteArrLen, cmpHot); //按热度排序
for (int time = 0; time < int(timeSeqName.size()); ++time) {
if (time <= 0.95 * timeSeqName.size())
allocateBandwith(time, output);
else
allocateBandwith2(time, output);
}
output.close();
// system("truncate -s -1 /output/solution.txt");
return 0;
}

评论