#P19011. [Roi2026]分布式系统
[Roi2026]分布式系统
题目描述
一家公司有 台服务器,编号为 到 。最初,第 台服务器上运行着 个服务。
服务器可能发生故障,因此公司为每台服务器指定了一台备用服务器:第 台服务器的备用服务器编号为 。若 ,则第 台服务器具有高可靠性,永远不会发生故障。
不同服务器的备用服务器互不相同。因此, 是 到 的一个排列。
当第 台服务器发生故障时,它当前运行的全部服务都会转移到第 台服务器上。随后,第 台服务器被一台没有运行任何服务的新服务器替换。服务器编号及其备用服务器编号保持不变。服务转移和服务器替换的过程非常快,在此期间不会发生其他故障。
公司准备测试系统的可靠性,使服务器依次发生故障,故障次数不超过 。任意两次故障都不会同时发生。
请问,经过不超过 次故障后,同一台服务器上最多可能运行多少个服务?
输入格式
第一行包含两个整数 (),分别表示服务器数量和最多允许的故障次数。
第二行包含 个整数 (),表示最初各台服务器上运行的服务数量。
第三行包含 个整数 (),表示备用服务器编号。保证 是一个排列。
输出格式
输出一个整数,表示一台服务器上可能运行的最多服务数量。
子任务与评分
| 子任务 | 分值 | 附加限制 | 必要子任务 |
|---|---|---|---|
| 1 | 15 | 无 | |
| 2 | 27 | 样例、1 | |
| 3 | 21 | 无 | |
| 4 | 37 | 无 | 样例、1、2、3 |
每个子任务内的全部测试点及必要子任务均通过,才获得该子任务的分数。样例为子任务 0。
样例 1
4 2
6 10 7 9
2 3 4 1
26
样例 2
3 1
1000000000 993 2010
1 3 2
1000000000
样例 3
11 5
3 5 12 7 5 9 2 6 0 9 4
2 8 9 6 5 11 3 1 10 7 4
23
样例说明
样例 1 中,先使服务器 2 故障,其 10 个服务转移到服务器 3,服务器 3 上共有 个服务;再使服务器 3 故障,17 个服务转移到服务器 4,使其运行 个服务。
| 阶段 | 服务器 1 | 服务器 2 | 服务器 3 | 服务器 4 |
|---|---|---|---|---|
| 最初 | 6 | 10 | 7 | 9 |
| 服务器 2 故障后 | 0 | 17 | ||
| 服务器 3 故障后 | 0 | 26 |
若反过来先使服务器 3 故障,再使服务器 2 故障,服务数量依次变为 和 ,最多只有 16 个服务,因此故障顺序会影响答案。
样例 2 中,可以不发生任何故障,服务器 1 上已有 个服务。服务器 1 的备用服务器是自身,所以它永远不会故障。使服务器 2 或 3 故障也不会改变答案。