CodeCraft-2021

复赛赛题和数据集

策略

• 部署：先处理大的虚拟机，后处理小的。
  1. 将每天的请求分为按删除操作分割的一段段的添加操作。每次处理一段添加操作。
  2. 将一段添加操作按照资源需求量从大到小排序。即先处理资源要求大的虚拟机，后处理资源要求小的。
  3. 为每个虚拟机选择服务器的策略：选定一种代价函数（考虑剩余资源和两类资源的平衡性），遍历所有服务器，选出代价最小的服务器进行部署。
• 迁移：尽量多迁移。
  1. 将服务器按照所剩资源从从到大排序。
  2. 从左到右遍历，对于每台服务器的每个虚拟机，从右往左遍历服务器直到找到能够容纳得下这个虚拟机的服务器，进行迁移。
• 购买：买一种，以最佳服务器去逼近总体的期望，效果不会太差
  1. 有K天的滑动窗口，即我们每天都能够看到未来K天的请求。
  2. 首先计算出未来K天的的所有添加请求的c/m。（即核数和内存的比值）。
  3. 每天固定买一种，即某一天的所有购买需求，都只买一种服务器：遍历所有可购服务器，选择一种既便宜其c/m又很接近2中求出来的值。
• 大规模迁移：将唯一的大规模迁移机会用在后面。
  1. 后2/3中首次有大规模迁移需求的那天。
  2. 后2/3中删除次数比前1/3天中删除次数最大值还要的那一天。