amazon 笔试

举例:

n个节点

v=[1,2,3...]

r=[3,2,1...]

k=2

注：这里v，r，k都是随机给的

一次操作：

• 消耗v中每个r值大于0的节点的和
• 能使某个节点的r值减k，如果某个节点的r值<=0了，节点之和就不算这个节点

求使每个节点<=0最少的消耗数

这个例子的最小消耗数求解如下：

1. 操作第三个节点，第三个节点r值减去k -> r=[3,2,-1] 此时消耗1+2+3=6
2. 操作第二个节点，第二个节点r值减去k -> r=[3,0,-1] 此时消耗1+2=3
3. 操作第一个节点，第一个节点r值减去k -> r=[1,0,-1] 此时消耗1
4. 操作第一个节点，第一个节点r值减去k -> r=[-1,0,-1] 此时消耗1
5. 最终消耗6+3+1+1=11，可以发现11是最少的消耗