题解 CF435B 【Pasha Maximizes】

2018-11-03 12:06:10


人生第一道灰题。

从最后结果最大的角度出发,从高到低考虑每一位,在能够变到该位的所有位中选择一个最大的变过来。

举个例子:

1423 2

$4$ 和 $2$ 都可以变到 $1$ 这里来。选择一个最大的变过来,就变成了 $4123$ 。

当然现在只转了一次,还可以转一次。

那么考虑第二位 $1$ ,此时只有 $2$ 可以变过来。所以最后产生的最大的数就是 $4213$ 。

大致思路就是这样,时间复杂度为 $O(n^2)$ , $n$ 是数的长度

细节见代码

我们考这题的时候还有多组数据,还有n≤50。。。