如何以最少的步数使序列成为非递减序列？

Question

这里的问题指出,

给定N个整数序列.在每一步中,允许将任何数字的值增加1或将其减少1.游戏的目标是使序列不减少,步数最少

例如,给定

3 2 -1 2 11

可以使该序列在4个步骤中成为非递减序列(将3减1并将-1增加3).

 (-1) (0) (+3) (0) (0)

序列将成为

2 2 2 2 11

我怎么解决这个问题？

Answer 1

好吧，这个问题表明你应该努力实现最少的更改。假设最后一个数字是 -1000000。如果按顺序运行该序列，最终将不得不在最后一个元素上添加 1000002 以获得非递减序列，但该解决方案将无法满足使用最少步数的要求。因此，最好运行一次序列，记录元素之间的差异。希望你明白我的意思。（我的书面想法并不像我自己看到的那么清晰:-)