csraf / codecraft-2021

CodeCraft-2021

华为软件精英赛2021-京津东北赛区(海盗团 Nine98, Csraf, dl) 初赛 4 复赛 9

---

初赛

购买策略

• 价格低者优先

迁移策略

• 思路: 为原本剩余资源多的服务器腾出更多空间, 以满足后序更大请求.
• 做法:
  • 常规: 排序所有的服务器, 剩余资源多者优先, 从左到右遍历源服务器, 从右往左遍历目的服务器, 遍历源服务器上 的虚拟机列表, 依次迁移到目的服务器上.
  • 贪心: 正式赛数据集较大, 考虑贪心, 对源服务器上的虚拟机列表排序, 剩余资源少者优先, 如果该虚拟机能迁移到 目的服务器上, 就迁移, 如果后序虚拟机仍然可以迁移到该目的服务器上, 继续迁移, 否则, 访问下一个目的服务器.

部署策略

• 对虚拟机请求进行排序, 请求资源多者优先, 对服务器列表进行排序, 剩余资源少者优先
• 贪心, 部署虚拟机时, 依次遍历服务器列表, 如果资源符合要求, 直接放入

---

复赛

题目改动

• 交互式环境: 无法直接读入所有天, (输出完一天的请求, fflush 处理缓冲区)
• 迁移次数增加: 0.5% -> 3% -> 100% (one day) + 3% (other day)

魔法

• 第一天预购买多个服务器
• 前 1/3 天, 购买策略: 服务器成本+能耗成本*剩余天数 低者优先, 后 2/3 天, 购买策略服务器成本低者优先
• 部署虚拟机到服务器时, 判断服务器是否满足 虚拟机资源*2.

单双节点分治

• 构造单节点服务器列表, 只部署单节点请求, 单节点请求只能在单节点服务器列表中迁移
• 构造双节点服务器列表, 只部署双节点请求, 双节点请求只能在双节点服务器列表中迁移
• 请求列表, 要按照先单节点后双节点的顺序来.