要想让整个数最大,就要让高位上的数尽可能大。但是,若要把一个数向前交换 x 个位置,这个数就要 −x, 由于每一位上的数都是 ≤9,所以我们就可以确定,对于每一个数,它最多往前移 9 个格子。所以,对于每一位,我们考虑将它后面的 9 个格子上的数移到这个位置上,取这个格子上的数和后面 9 个格子上的数移到这个位置上的值取最大值。这步操作为常数级别,所以总时间复杂度为 O(n)。
By signing up a wangzaioj universal account, you can submit code and join discussions in all online judging services provided by us.
Using your wangzaioj universal account