题解

「XXI Olimpiada Informatyczna」超级计算机 题解

题目分析

给定一棵指令树，根节点是指令 1。每个处理器每单位时间可以执行一条指令，执行完一条指令后其所有子指令变为可执行状态。有 $k$ 个处理器时，每单位时间最多执行 $k$ 条指令。需要计算对于不同的 $k$，最短的执行时间。

关键观察

1. 执行时间分析：执行时间由两部分组成：

   • 必须按顺序执行的部分（深度相关的串行时间）
   • 可以并行执行的部分（每层节点的并行调度）

2. 深度分布：树的深度分布决定了执行时间的下界

3. 处理器利用：当处理器数量足够多时，时间由树的深度决定；当处理器较少时，时间由节点总数和处理器数量决定

算法思路

1. 深度统计与后缀和

首先通过 DFS 统计每个深度的节点数量：

dfs(1, 0);  // 统计每个深度的节点数

然后计算后缀和：

for (int i = n; i >= 1; i--)
    a[i] += a[i + 1];

这里 a[i] 表示深度 ≥ $i$ 的节点总数。

2. 凸包优化

维护一个下凸壳，用于快速找到最优的深度分割点：

// 斜率计算函数
double slp(LL i, LL j) {
    return 1.0 * (a[i + 1] - a[j + 1]) / (i - j);
}

// 构建凸壳
for (int i = 1; i <= mx; i++) {
    while (top >= 2 && slp(st[top - 1], i) <= slp(st[top], i))
        top--;
    st[++top] = i;
}

3. 查询处理

对于每个处理器数量 $k$：

ans[k] = st[top] + (a[st[top] + 1] + k - 1) / k;

其中：

• st[top] 是最优的深度分割点
• (a[st[top] + 1] + k - 1) / k 计算剩余节点需要的轮数

算法复杂度

• DFS 遍历：$O(n)$
• 凸壳构建：$O(n)$（每个点最多进出一次）
• 查询处理：$O(N)$，其中 $N = 10^6$
• 总复杂度：$O(n + N)$，可以处理 $n, q \le 10^6$ 的数据

算法正确性

该算法基于以下观察：

1. 执行时间 ≥ 树的深度
2. 执行时间 ≥ ⌈总节点数 / 处理器数⌉
3. 通过凸包优化找到深度和并行执行的最优平衡点

总结

本题通过巧妙的深度统计和凸包优化技术，将复杂的并行调度问题转化为数学模型求解。算法在线性时间内完成预处理，可以快速回答大量查询。

最终算法标签： 树遍历 深度统计 凸包优化 斜率优化 后缀和 离线查询