刷题笔记合集🔗

高矮个子排队

问题描述

有一队小朋友站成一排，他们的身高各不相同。我们用一个正整数数组来表示这队小朋友的身高，例如 {}。

现在我们希望将这些小朋友重新排队，使他们按照"高""矮""高""矮"的顺序排列。具体要求如下：

1. 每个"高"位置的小朋友要比相邻位置的小朋友高或者一样高。
2. 每个"矮"位置的小朋友要比相邻位置的小朋友矮或者一样矮。
3. 小朋友们移动的总距离要最小。
4. 排队从"高"位置开始。

例如，对于小队 {}，一个满足条件的排序结果是 {}。

注意，虽然 {} 也满足"高""矮""高""矮"的顺序，但小朋友们的移动距离较大，所以不是最优结果。

移动距离的定义如下：

• 如果一个小朋友从第二位移到第三位，移动距离为 。
• 如果移动到第四位，移动距离为 ，以此类推。

输入格式

输入为一行，包含若干个用空格分隔的正整数，表示小朋友们的身高。

输出格式

输出为一行，包含若干个用空格分隔的正整数，表示重新排序后小朋友们的身高。

样例输入1

4 1 3 5 2

样例输出1

4 1 5 2 3

样例输入2

1 1 1 1 1

样例输出2

1 1 1 1 1

样例输入3

xxx

样例输出3

[]

样例解释

数据范围

• 小朋友数量 满足
• 身高 满足

题解

模拟排序

这道题目要求我们将一队小朋友按照"高""矮""高""矮"的顺序重新排列，同时要求移动距离最小。解题的关键在于理解题目要求和找到一个高效的排序方法。

首先，我们需要明白"高""矮"交替的含义：

1. 奇数位置（第1、3、5...位）的小朋友应该比相邻的小朋友高或相等。
2. 偶数位置（第2、4、6...位）的小朋友应该比相邻的小朋友矮或相等。

解决这个问题的一个有效方法是使用冒泡排序的思想，但我们只需要进行一次遍历：

1. 从左到右遍历数组。
2. 对于奇数位置，如果当前小朋友比右边的矮，就交换它们。
3. 对于偶数位置，如果当前小朋友比右边的高，就交换它们。

这个方法之所以有效，是因为：

1. 它保证了奇数位置的小朋友总是不低于偶数位置的小朋友。
2. 每次交换都是相邻位置的交换，保证了移动距离最小。
3. 一次遍历就能完成排序，因为我们只需要保证相邻位置的大小关系正确。

时间复杂度分析：

• 算法只需要遍历一次数组，所以时间复杂度是 ，其中 是小朋友的数量。
• 对于给定的数据范围（），这个复杂度是完全可以接受的。

需要注意的是，我们还需要处理输入可能非法的情况，比如输入不是数字时，应该返回空数组。

这个解法的优点是简单直观，容易实现，而且能够保证最小的移动距离。

参考代码

• Python

def rearrange_heights(heights):
    # 检查输入是否合法
    if not all(isinstance(h, int) and h > 0 for h in heights):
        return []
    
    n = len(heights)
    # 如果只有一个小朋友，直接返回
    if n == 1:
        return heights
    
    # 遍历数组，调整相邻小朋友的位置
    for i in range(n - 1):
        if i % 2 == 0:  # 奇数位置（索引从0开始）
            if heights[i] < heights[i + 1]:
                heights[i], heights[i + 1] = heights[i + 1], heights[i]
        else:  # 偶数位置
            if heights[i] > heights[i + 1]:
                heights[i], heights[i + 1] = heights[i + 1], heights[i]
    
    return heights

# 读取输入
try:
    heights = list(map(int, input().split()))
    result = rearrange_heights(heights)
    print(' '.join(map(str, result)))
except ValueError:
    print('[]')

• C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_N 100

// 交换两个整数
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 重新排列小朋友的身高
void rearrange_heights(int *heights, int n) {
    for (int i = 0; i < n - 1; i++) {
        if (i % 2 == 0) {  // 奇数位置
            if (heights[i] < heights[i + 1]) {
                swap(&heights[i], &heights[i + 1]);
            }
        } else {  // 偶数位置
            if (heights[i] > heights[i + 1]) {
                swap(&heights[i], &heights[i + 1]);
            }
        }
    }
}

int main() {
    char input[1000];
    int heights[MAX_N];
    int n = 0;

    // 读取输入
    if (fgets(input, sizeof(input), stdin) == NULL) {
        printf("[]\n");
        return 0;
    }

    // 解析输入
    char *token = strtok(input, " \n");
    while (token != NULL && n < MAX_N) {
        // 检查是否为有效的正整数
        int valid = 1;
        for (int i = 0; token[i]; i++) {
            if (!isdigit(token[i])) {
                valid = 0;
                break;