比如说当我们往6的左边填入一个数字时,因为6相对1已经是距离最大值,而向左填入会导致y坐标减1,那么填入的数字只能比6更小。...3
0 2 0
3 0 1
那么这里的交换其实就是:
[3,0,1,2,3] 原始是[3,0,1],第一次操作后是[0,1,2],第二次操作之后是[1,2,3],满足要求;
3
0 2 0...1 0 3
[1,0,3,0,1,2,3] 是第二样例;
总结前面的思路,就是不断拿0去交换b里面的数字,直到a里面的数字可以开始填1、2、3...;
现在的问题是如何断定1开始填是可以的?...容易知道如果从第x个位置开始填入有解,那么从第x+1个位置开始填也是有解。
那么可以从[1, n]二分,最终得到一个有效的解。
这里需要考虑一种特殊情况,就是填充的数字不是从1开始的。...0,延后1的插入位置,那么2、3、4、、等所有的位置都会延后;
直到所有的数字插入完毕。