E-高矮个子排队 (100分)
刷题笔记合集🔗
高矮个子排队
问题描述
有一队小朋友站成一排,他们的身高各不相同。我们用一个正整数数组来表示这队小朋友的身高,例如 {}。
现在我们希望将这些小朋友重新排队,使他们按照"高""矮""高""矮"的顺序排列。具体要求如下:
- 每个"高"位置的小朋友要比相邻位置的小朋友高或者一样高。
- 每个"矮"位置的小朋友要比相邻位置的小朋友矮或者一样矮。
- 小朋友们移动的总距离要最小。
- 排队从"高"位置开始。
例如,对于小队 {},一个满足条件的排序结果是 {}。
注意,虽然 {} 也满足"高""矮""高""矮"的顺序,但小朋友们的移动距离较大,所以不是最优结果。
移动距离的定义如下:
- 如果一个小朋友从第二位移到第三位,移动距离为 。
- 如果移动到第四位,移动距离为 ,以此类推。
输入格式
输入为一行,包含若干个用空格分隔的正整数,表示小朋友们的身高。
输出格式
输出为一行,包含若干个用空格分隔的正整数,表示重新排序后小朋友们的身高。
样例输入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、3、5...位)的小朋友应该比相邻的小朋友高或相等。
- 偶数位置(第2、4、6...位)的小朋友应该比相邻的小朋友矮或相等。
解决这个问题的一个有效方法是使用冒泡排序的思想,但我们只需要进行一次遍历:
- 从左到右遍历数组。
- 对于奇数位置,如果当前小朋友比右边的矮,就交换它们。
- 对于偶数位置,如果当前小朋友比右边的高,就交换它们。
这个方法之所以有效,是因为:
- 它保证了奇数位置的小朋友总是不低于偶数位置的小朋友。
- 每次交换都是相邻位置的交换,保证了移动距离最小。
- 一次遍历就能完成排序,因为我们只需要保证相邻位置的大小关系正确。
时间复杂度分析:
- 算法只需要遍历一次数组,所以时间复杂度是 ,其中 是小朋友的数量。
- 对于给定的数据范围(),这个复杂度是完全可以接受的。
需要注意的是,我们还需要处理输入可能非法的情况,比如输入不是数字时,应该返回空数组。
这个解法的优点是简单直观,容易实现,而且能够保证最小的移动距离。
参考代码
- 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%内容,订阅专栏后可继续查看/也可单篇购买
算法刷题笔记 文章被收录于专栏
本专栏收集并整理了一些刷题笔记