本题先进行一下转换。将每行末尾的零的个数统计一下,得到数组zeros,即zeros[i]表示第i行末尾的零的个数。我们的目标是将zeros通过adjacent swap操作,变成一个数组target,其中target[i]>=n-1-i. 求最小的操作数。
我们首先考虑target[0],它的要求最高(需要有n-1个零)。我们考察所有的行,看看有哪些满足条件。加入有a和b两行满足条件,即zeros[a]>=n-1,zeros[b]>=n-1,那么我们应该选择将哪一行挪到第0行的位置上来呢?我们不妨举个例子:
X X X a X b X
如果我们选择将第b行提到最前面,那么需要操作5次得到
b X X X a X X (1)
如果我们选择将第a行提到最前面,那么需要操作3次得到
a X X X X b X (2)
别停,我们如果对(2)继续操作1次(将b前移一位)能得到
a X X X b X X (3)
我们比较一下(1)和(3)。我们发现对于第0行的处理,两种方案都满足条件。唯一的区别是,第一种方案第4行是zeros[a],第二种方案第4行是zeros[b]。但是由于zeros[a]和zeros[b]都是大于等于n-1的,而除了target[0]之外的target[i]的要求都不到n-1,所以这两行(a和b)对于以后的安排而言都是“溢价”的,即“价值”是没有区别的。但是第一种方案需要5次操作,第二种方案只需要4次操作。
所以我们得到一个贪心的结论:当我们处理target[i]时需要找某个zeros[j]>=n-1-i时,只要从i开始往后顺次查找第一个满足zeros[j]>=n-1-i的位置即可。然后将j所对应的行提前到第i行。然后处理target[i+1],不断重复。