Citadel OA 真题复盘｜进程分配 + 负载均衡两道题完整解析
导读：Citadel 的 OA 考试以系统设计和算法优化著称。这两道题考察的是分布式系统中的核心问题：如何高效分配进程资源，以及如何动态平衡处理器负载。第一题考察组合数学，第二题考察二分查找与贪心策略。
📌 题目一：进程分配方案计数
问题描述
将 n 个进程分配到 k 个处理器，要求相邻进程不能使用同一处理器。求满足条件的分配方案总数，结果对给定模数取模。
示例：
- n = 2, k = 3：第一个进程有 3 种选择，第二个进程有 2 种选择（不能与第一个相同），总方案数 = 3 × 2 = 6
- n = 1, k = 3：只有 1 个进程，方案数 = 3
- n = 3, k = 2：方案数 = 2 × 1 × 1 = 2
核心思路
这是一个组合数学问题，使用动态规划或数学公式求解。
方法一：数学公式（最优）
关键观察：
- 第 1 个进程：有 k 种选择
- 第 2 到第 n 个进程：每个都有 k-1 种选择（不能与前一个相同）
公式：
总方案数 = k × (k-1)^(n-1)
特殊情况：
- 若 n = 1，返回 k
- 若 k = 1 且 n > 1，返回 0（无法满足相邻不同的条件）
方法二：动态规划
定义 dp[i][j] 表示前 i 个进程分配到处理器 j 的方案数。
def count_allocations_dp(n, k, mod):
if n == 1:
return k % mod
if k == 1:
return 0
# dp[i][j] = 前i个进程，第i个分配到处理器j的方案数
dp = [[0] * k for _ in range(n + 1)]
# 初始化：第1个进程可以分配到任何处理器
for j in range(k):
dp[1][j] = 1
# 填充DP表
for i in range(2, n + 1):
for j in range(k):
# 第i个进程分配到处理器j
# 第i-1个进程必须不在处理器j
for prev_j in range(k):
if prev_j != j:
dp[i][j] = (dp[i][j] + dp[i-1][prev_j]) % mod
# 求和所有可能的最后一个处理器
result = sum(dp[n]) % mod
return result
时间复杂度：O(n × k²)
空间复杂度：O(n × k)
最优解：数学公式 + 快速幂
def count_allocations(n, k, mod):
"""
计算进程分配方案数
Args:
n: 进程数
k: 处理器数
mod: 模数
Returns:
方案总数 % mod
"""
if n == 1:
return k % mod
if k == 1:
return 0
# 计算 k × (k-1)^(n-1) % mod
# 使用快速幂优化
base = (k - 1) % mod
power = pow(base, n - 1, mod) # Python内置快速幂
result = (k % mod * power) % mod
return result
时间复杂度：O(log n)
空间复杂度：O(1)
完整代码
def processScheduling(n, k, mod):
"""
Q1: 进程分配方案计数
将n个进程分配到k个处理器，相邻进程不能使用同一处理器
求方案总数 % mod
"""
# 特殊情况处理
if n == 1:
return k % mod
if k == 1:
return 0
# 公式：k × (k-1)^(n-1)
# 使用Python内置pow函数进行快速幂运算
result = (k % mod) * pow(k - 1, n - 1, mod) % mod
return result
# 测试用例
if __name__ == "__main__":
MOD = 10**9 + 7
# 测试1
print(processScheduling(2, 3, MOD)) # 输出: 6
# 测试2
print(processScheduling(1, 3, MOD)) # 输出: 3
# 测试3
print(processScheduling(3, 2, MOD)) # 输出: 2
# 测试4：大数据
print(processScheduling(1000000, 1000000, MOD)) # 快速计算
面试要点
✅ 澄清问题：
- 进程是否有顺序？（是的，相邻指的是序列中的相邻）
- 模数是多少？（通常是 10^9+7）
- n 和 k 的范围？（影响算法选择）
✅ 优化思路：
- 从 DP 优化到数学公式（O(n×k²) → O(log n)）
- 使用快速幂处理大数据
❌ 常见错误：
- 忘记处理 k=1 的特殊情况
- 没有使用快速幂，导致超时
- 模运算顺序错误
📌 题目二：处理器负载均衡最小轮次
问题描述
系统有 k 个处理器，初始任务分配为 tasks[0..k-1]。每一轮中：
- 每个处理器可以处理一个任务（任务数减 1）
- 或者将一个任务转移给其他处理器
求完成所有任务的最小轮次，使得所有处理器的负载均衡。
示例：
k = 3, tasks = [1, 2, 3]
初始状态：处理器0有1个任务，处理器1有2个任务，处理器2有3个任务
第1轮：
- 处理器0处理1个任务 → 剩余0个
- 处理器1处理1个任务，转移1个给处理器0 → 剩余1个
- 处理器2处理1个任务，转移1个给处理器1 → 剩余1个
第2轮：
- 处理器0处理1个任务 → 剩余0个
- 处理器1处理1个任务 → 剩余0个
- 处理器2处理1个任务 → 剩余0个
最小轮次 = 2
核心思路
使用二分查找答案。对于给定的轮次 t，检查是否可行。
可行性检查
对于轮次 t，每个处理器最多可以处理 t 个任务。
关键计算：
- 若处理器 i 初始有
cnt[i]个任务：- 若
cnt[i] > t：多出need = cnt[i] - t个任务需要转移给其他处理器 - 若
cnt[i] ≤ t：剩余可用容量avail = (t - cnt[i]) / 2（向下取整）- 为什么除以 2？因为每个任务转移需要 1 轮时间，处理也需要 1 轮时间
- 若
可行条件：所有处理器的总可用容量 ≥ 总需转移任务数
def is_feasible(tasks, k, t):
"""
检查轮次t是否可行
"""
need = 0 # 需要转移的任务总数
avail = 0 # 可用容量总数
for cnt in tasks:
if cnt > t:
need += cnt - t
else:
avail += (t - cnt) // 2
return avail >= need
二分查找
def minRounds(tasks, k):
"""
二分查找最小轮次
"""
# 最坏情况：所有任务都在一个处理器上
left, right = 1, max(tasks)
while left < right:
mid = (left + right) // 2
if is_feasible(tasks, k, mid):
right = mid
else:
left = mid + 1
return left
完整代码
def getMinTime(k, tasks):
"""
Q2: 处理器负载均衡最小轮次
Args:
k: 处理器数量
tasks: 初始任务分配数组，tasks[i]表示处理器i的任务数
Returns:
完成所有任务的最小轮次
"""
def is_feasible(t):
"""检查轮次t是否可行"""
need = 0 # 需要转移的任务总数
avail = 0 # 可用容量总数
for cnt in tasks:
if cnt > t:
# 处理器任务过多，需要转移
need += cnt - t
else:
# 处理器有剩余容量
# 可用容量 = (t - cnt) // 2
# 原因：转移1个任务需要1轮，处理需要1轮，共2轮
avail += (t - cnt) // 2
return avail >= need
# 二分查找最小轮次
left, right = 1, max(tasks)
while left < right:
mid = (left + right) // 2
if is_feasible(mid):
right = mid
else:
left = mid + 1
return left
# 测试用例
if __name__ == "__main__":
# 测试1
print(getMinTime(3, [1, 2, 3])) # 输出: 2
# 测试2
print(getMinTime(2, [5, 5])) # 输出: 5
# 测试3
print(getMinTime(4, [1, 1, 1, 1])) # 输出: 1
# 测试4：不均衡
print(getMinTime(2, [10, 1])) # 输出: 5
复杂度分析
时间复杂度：O(k × log(max(tasks)))
- 二分查找：O(log(max(tasks)))
- 每次检查：O(k)
空间复杂度：O(1)（不计输入）
面试要点
✅ 澄清问题：
- 任务转移是否需要时间？（是的，需要 1 轮）
- 一个处理器一轮最多处理几个任务？（1 个）
- 目标是什么？（最小化总轮次）
✅ 关键洞察：
- 二分查找答案空间（轮次）
- 理解可用容量的计算（为什么除以 2）
- 贪心策略：优先处理任务多的处理器
❌ 常见错误：
- 没有正确理解可用容量的计算
- 二分查找边界条件错误
- 忽视任务转移的时间成本
🎯 总结对比
| 题目 | 算法 | 时间复杂度 | 难度 |
|---|---|---|---|
| Q1：进程分配 | 组合数学 + 快速幂 | O(log n) | ⭐⭐ |
| Q2：负载均衡 | 二分查找 + 贪心 | O(k log m) | ⭐⭐⭐ |
🚀 面试建议
- 时间管理：两道题共 90 分钟，建议各 45 分钟
- 代码质量：注重边界条件和模运算
- 沟通能力：清晰解释算法思路和复杂度
- 优化意识：从暴力解到最优解的演进过程
📞 需要面试辅助？
oavoservice 提供专业的 OA/VO 辅助服务。
👉 立即添加微信：Coding0201