E-高矮个子排队 (100分)

刷题笔记合集🔗

高矮个子排队

问题描述

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

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

  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 输出结果满足"高""矮""高""矮""高"的顺序,且移动距离最小。只有 5 和 3 交换了位置,移动距离都是 1。
样例2 当所有小朋友身高相同时,原序列已经满足条件,不需要移动。
样例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;
         

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

算法刷题笔记 文章被收录于专栏

本专栏收集并整理了一些刷题笔记

全部评论

相关推荐

1 1 评论
分享
牛客网
牛客企业服务