解题思路
题面已经把策略写死,本质是按规则模拟,而不是另寻最优划分。
- 先算每波容量。记 q=⌊p/b⌋,r=pmodb,则前 b−r 波容量为 q,最后 r 波容量为 q+1。余数一定摊在末尾,不能摊到前几波。
- 从第 1 波填到第 b 波。每个波次单独维护 d 个集合:该维在本波次里已经出现过的标签。换波次时集合清空。
- 波次内每要再拿一台,就扫所有未入选主机,算增量:该机第 j 维标签若不在本波次第 j 个集合里,就加 1。增量最大者入选;增量相同取 nid 更小的。入选后把它的各维标签写入本波次集合,并标记已用。
- 一个波次刚开始时集合是空的,所有剩余主机增量都等于 d,因此每波第一个一定是当前剩余 nid 最小的那台。后面几台才会因增量拉开差距。
- 该波次名单收集齐后按 nid 升序输出。常见假解:余数加到前几波、增量相对「全局已选」而不是「本波次」、维度混成一个集合、增量打平时取大编号、输出不排序。