P5469. 主机灰度分批

场次：2026年9月18日-非AI方向 · 来源：CodeFun2000 P5469

题目描述

云上要给一大批计算节点做版本滚动。为了把风险压住，升级会拆成若干波次，也就是常说的灰度放量。

越靠前的波次越希望把各类机型都点到，好尽早把隐患暴露出来。

任务描述

手里有 $p$ 台主机，每台带着 $d$ 个维度的标签（比如板型、系统发行版）。某一维上标签相同，就认定这两台在该维属于同一类。

请按下面的规则排出分波方案：越靠前的波次，标签种类要尽量铺得开。

核心规则

1. 波次容量：

   主机总数记为 $p$，波次总数记为 $b$。

   • 基准容量 $q=\lfloor p/b\rfloor$。
   • 余数 $r=p\bmod b$。
   • 前 $b-r$ 个波次容量都是 $q$，最后 $r$ 个波次容量都是 $q+1$。

2. 增量尽量大：

   填当前波次时，只能从未入选的主机里挑。看哪一台还能给本波次补进最多尚未出现的标签。

   • 增量：该机某个维度上的标签，若本波次已入选的机器里还没出现过，就记一分。
   • 先比增量，越大越先拿。
   • 增量打平则拿 $nid$ 更小的那台。

3. 执行顺序：

   从第 $1$ 波填到第 $b$ 波，每波填满为止。某台一旦进了某一波，后面的波次不再考虑它。

输入格式

1. 首行两个整数 $p$ 和 $d$，即主机台数与标签维度。$(1\le p\le 2\times 10^{2},\ 1\le d\le 2)$

2. 随后 $p$ 行：每台主机一行，格式为

   nid tag_1 tag_2 ... tag_d

3. 末行一个整数 $b$，即波次总数。$(1\le b\le 2\times 10^{1})$

输出格式

输出 $b$ 行。第 $i$ 行给出该波次里的 $nid$，同一行按数值升序，相邻编号用空格隔开。

示例

示例 1

输入：

4 1
10 A
11 A
12 A
13 A
2

输出：

10 11
12 13

说明：

• $4\div 2=2$ 余 $0$，两波容量都是 $2$。
• 标签全是 $A$，第一台进波次后其余增量都变成 $0$。
• 增量打平时按 $nid$ 从小到大，故第一波 $10\ 11$，其余进第二波。

示例 2

输入：

6 2
1 X P
2 X Q
3 Y P
4 Y Q
5 Z Q
6 Z R
2

输出：

1 4 6
2 3 5

说明：

• $6\div 2=3$ 余 $0$，两波容量都是 $3$。
• 第一波：空盘先拿 $nid=1$（增量 $2$）；已有 $\{X,P\}$ 后再拿 $nid=4$（增量 $2$）；已有 $\{X,Y,P,Q\}$ 后再拿 $nid=6$（增量 $2$）。
• 剩下 $2,3,5$ 进第二波。

提示

1. 多样性按各维标签种类相加；越靠前的波次越优先把种类铺开。
2. 容量：总数 $p$、波次 $b$，基准是 $\lfloor p/b\rfloor$，多出来的台数摊到最后若干波。