大鱼吃小鱼Q18

微软面试题

背景

鱼与尺寸

在一个鱼塘里 有一堆鱼 $f_1 ... f_n$

第 $i$ 只鱼的大小为 $s_i$

每只鱼刚开始的大小均为 1

吃鱼规则

当一只鱼 $f_a$ 的尺寸 $s_a$ 大于等于 另外一只鱼 $f_b$ 的尺寸 $s_b$ 时，

$f_a$ 可以吃掉 $f_b$。

吃掉后 $f_a$ 的尺寸变为 $s_a+s_b$，而 $f_b$ 的尺寸变为 0

要求

输入

给定 n 只鱼，和 一个指令数组

指令数组 的每个元素为一个2个元素的数组

比如

1, 1
1, 2
3, 1

每一行的为指令，代表 左边数字的那只鱼 要吃掉 右边的那只鱼

输出

返回一个 n 尺寸的数组，

如果该鱼没有被吃，则为 0。

如果被吃了，则显示为 现在它在哪只鱼的肚子里

案例

假设 n 是 3

假设指令数组为

1, 1        
1, 2
3, 2
3, 1

第一条指令不能执行，因为自己不能吃自己

第二条指令可以执行，执行后，第一条鱼的大小为 2， 第二条鱼的大小为 0

第三条指令不能执行，因为 第2条鱼 已经被吃到 第1条鱼的肚子里了

第四条指令不能执行，因为 第3条鱼的尺寸 小于 第1条鱼的尺寸

目前为止鱼 1 和 3 还活着，尺寸分别是 2，1

鱼 2 在 1 的肚子里

需要返回

[0, 1, 0]

API

start(n: Int, commands: Int) : Int