2 考慮經上下排序後的某兩相鄰直行。
(1,1) (1,2)
(2,1) (2,2)
(3,1) (3,2)
... ...
已知(1,n)<=(2,n)<=(3,n)......
設(1,2)本來位於(m,1)右邊,易知(1,2)>=(m,1)>=(1,1),亦即(1,1)<=(1,2)
考慮(1,2)於排序前的位置.
1:若(1,2)本來位於(1,1)右邊,考慮(2,2)本來的位置,易知(2,1)<=(2,2)
2.若(1,2)本來位於(n,1)右邊(n>=2),那麼(2,2)>=(1,2)>=(n,1)>=(2,1),亦即(2,1)<(2,2)
考慮(1,2),(2,2)...(n-1,2)這些元素本來的位置.
若其與(1,1),(2,1)...(n-1,1)等自相配對,考慮(n,2)本來的位置,再次易知(n,1)<=(n,2)
若其中至少一個元素(a,2)與(k,1)配對(k>=n),那麼(n,2)>=(a,2)>=(k,1)>=(n,1),亦即(n,1)<=(n,2)
-----------------------------------------------------------
我發現我的表達能力真的好差... |