我要招人

去企业版

首页 > 试题广场 >

小美的排列构造

[编程题]小美的排列构造

热度指数：2609 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小美定义一个数组 $a$ 的权值计算如下：

首先将 $a$ 的每一对相邻两项求和，得到一个 $b$ 数组。那么 $b$ 数组的最大值减最小值即为 $a$ 数组的权值。

例如，若 $a=[2,1,3]$ ，那么 $b=[3,4]$ ， $b$ 数组的极差是1。因此 $a$ 数组的权值为1。

现在小美希望你能构造一个长度为 $n$ 的排列，满足权值尽可能小。你能帮帮她吗？

排列是指一个长度为 $n$ 的数组，其中 1 到 $n$ 每个元素恰好出现一次。

输入描述:

一个正整数，代表排列的长度。

输出描述:

一个合法的排列。如果有多解输出任意即可。

示例1

输入

输出

2 1 3

说明

这个数组的权值为 1。输出[2,3,1]等排列也是合法的。

算法知识视频讲解

Python

suwueng

这个只要想到了一种排列方式就行，可以将数分成前后两部分，前一部分正序排列，后一部分逆序排列，两部分交错合并，就比如：

1～8:

step1 分为两部分，1 2 3 4 和 5 6 7 8

step2 后一部分逆序，变成1 2 3 4 和 8 7 6 5

step3 交错合并， 1 8 2 7 3 6 4 5

import sys

n = int(input())

m = n // 2
ans = []
for i in range(m):
    ans.append(i+1)
    ans.append(n - i)
if n % 2:
    ans.append(m + 1)
    for i in ans:
        print(i, end=' ')
else:
    for i in ans:
        print(i, end=' ')

发表于 2024-03-09 21:16:09 回复(1)

Python

秋招早日上岸

python,这道题的思路就是从一个1到n的数组中，重新排列，数字组间和之差最小。最理想的方案就是每次只取数组中的最大值和最小值.最终就会得到这样的一个数组[n,1, n-1,2, n-2,3, ..., n//2]，然后将数组逆序转换成字符串

def sol(n):
    arr = [i+1 for i in range(n)]
    arr.sort(reverse=True)
    ans = []
    left,right = 0,n-1
    while left<=right:
        if left == right:
            ans.append(arr[left])
            break
        ans.append(arr[left])
        ans.append(arr[right])
        left += 1
        right -=1
    str_ans = ' '.join([str(x) for x in ans[::-1]]).strip()
    return str_ans
while 1:
    try:
        n = int(input())
        ans = sol(n)
        print(ans)
    except:
        break

发表于 2023-10-21 02:40:37 回复(0)

Python

longkouding

import sys
 
for line in sys.stdin:
    a = line.split()
     
n = int(a[0])
res = [0 for i in range(n)]
max_n = n
min_n = 1
for i in range(1,n,2):
    res[i] = max_n
    max_n = max_n - 1
 
for i in range(0,n,2):
    res[i] = min_n
    min_n +=1
out = " ".join(str(r) for r in res)
print(out)

编辑于 2023-08-18 18:34:31 回复(0)

提交观点

问题信息

来自：美团2023年秋招笔试...

难度：

4条回答 45收藏 2104浏览

小美的排列构造

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题