活跃农民
- 积分
- 354
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2015-1-20
- 最后登录
- 1970-1-1
|
我理解你的困惑,不过你完全不需要担心那6种情况,因为你只需像我2楼中说的,做这么一件事:
对于连续的Ai~Aj,把Bi~Bj+1排序即可。
这就可以处理那6种情况了。
就用你的例子来说明
A= {0000} {11} {00} {1} {000} , B = {10, 9, 8, 7, 6}, {5,4},{11,12},{3},{9,8,7}
A0~A3是0,那么把B0~B4按降序排列,得
B = {10, 9, 8, 7, 6}, ....
A4~A5是1,那么把B4~B6按升序排列,得
B = {10, 9, 8, 7, 4}, {5, 6}...
A6~A7是0,那么把B6~B7按降序排列,得
B = {10, 9, 8, 7, 4}, {5, 12}, {7, 6}...
...
看,每次对Ai~Aj排序时,都要用到“之前已经被排好的序列的最后一个数字”,即Bi。可以这么做的理由是:
如果Bi~Bj+1应该是升序,那么Bi~Bj+1之前的序列Bi'~Bj'+1一定是降序(此处i=j'+1)。对Bi~Bj+1排序完以后,此时的Bi应当是Bi~Bj+1中的最小;由于排序后的Bi一定不大于排序前的Bi(也就是Bj'+1),那么既然原来的Bj'+1是Bi'~Bj'+1中的最小值,那么对Bi~Bj+1排序过后的Bi(也就是Bj'+1)一定还是Bi'~Bj'+1中的最小值。
如果Bi~Bj+1是降序,也可同理得出类似结论。
换言之。这种排序方法绝对不会改变之前已经得到的升降序列。可以放心使用。
QED
|
|