高矮个子排队

题目描述

现在有一队小朋友, 他们高矮不同, 我们以正整数数组表示这一队小朋友的身高, 如数组{5,3,1,2,3}.

我们现在希望小朋友排队, 以高矮高矮顺序排列, 每一个高位置的小朋友要比相邻的位置高或者相等; 每一个矮位置的小朋友要比相邻的位置矮或者相等

要求小朋友们移动的距离和最小, 第一个从“高”位开始排, 输出最小移动距离即可.

例如, 在示范小队{5,3,1,2,3}中, {5, 1, 3, 2, 3}是排序结果.

{5, 2, 3, 1, 3} 虽然也满足高矮高矮顺序排列, 但小朋友们的移动距离大, 所以不是最优结果.

移动距离的定义如下所示:

第二位小朋友移到第三位小朋友后面, 移动距离为1, 若移动到第四位小朋友后面, 移动距离为2.

输入描述

排序前的小朋友, 以英文空格的正整数:

4 3 5 7 8

注: 小朋友<100个

输出描述

排序后的小朋友, 以英文空格分割的正整数: 4 3 7 5 8

备注: 4 (高) 3 (矮) 7 (高) 5 (矮) 8 (高) , 输出结果为最小移动距离, 只有5和7交换了位置, 移动距离都是1.

示例1

输入:

4 1 3 5 2 

输出:

4 1 5 2 3

示例2

输入:

1 1 1 1 1 

输出:

1 1 1 1 1 

示例3

输入:

xxx

输出:

[ ]

示例4

输入:

4 3 5 7 8

输出:

4 3 7 5 8

示例5

输入:

5 3 1 2 3

输出:

5 1 3 2 3

题解

Python

def main():
    try:
        heights = list(map(int, input().split()))
    except ValueError:
        # Invalid input
        print("[]")
        return
    
    i = 0
    j = 1
    while j < len(heights):
        # 交换相邻小朋友的条件:
        # - 相邻的两个小朋友身高不相同
        # - 如果 i 是偶数, 并且 i 位小朋友的身高小于右侧 j 位的身高
        # - 如果 i 是奇数, 并且 i 位小朋友的身高大于右侧 j 位的身高
        if heights[i] != heights[j] and ((heights[i] > heights[j]) != (i % 2 == 0)):
            heights[i], heights[j] = heights[j], heights[i]
        i += 1
        j += 1

    print(" ".join(map(str, heights)))

if __name__ == "__main__":
    main()