列表

详情


NC256069. 游游的排列构造

描述

游游定义一个排列中,满足以下条件的为“好元素”:
对于第i个元素a_i而言,a_i为前i个元素的最大值。例如,[3,1,5,2,4]中,第一个和第三个元素是好元素。

游游希望你构造一个长度为n的排列,其中有k个好元素,且任意两个好元素都不相邻。你能帮帮她吗?

排列的定义:由 1 到 n所有正整数组成的长度为n的数组,每个正整数出现恰好一次。

输入描述

两个正整数n,k,用空格隔开。
1\leq n \leq 10^5
1\leq k \leq \lceil \frac{n}{2} \rceil

输出描述

一行n个正整数,代表游游构造的排列。有多解时输出任意即可。

示例1

输入:

5 2

输出:

3 1 5 2 4

示例2

输入:

5 3

输出:

2 1 4 3 5

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

Java 解法, 执行用时: 542ms, 内存消耗: 22244K, 提交时间: 2023-08-12 12:57:36

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		Scanner sc =new Scanner(System.in);
		int n=sc.nextInt();
		int k=sc.nextInt();//k<=n/2
		int[]  ch=new int[n];
		ch[0]=n-k+1;
		int j=1;
        for(int i=1;i<n;i++) {
        	if(i<2*k-1 && i%2==0) {
        		ch[i]=ch[i-2]+1;
        	}
        	else ch[i]=j++;
        }
        for(int c:ch)
		System.out.print(c+" ");
	}
}

Go 解法, 执行用时: 21ms, 内存消耗: 3004K, 提交时间: 2023-08-12 12:57:03

package main

import (
	"bufio"
	."fmt"
	"os"
)
func main() {
	in, out := bufio.NewReader(os.Stdin), bufio.NewWriter(os.Stdout)
	var n,k int
	Fscan(in,&n,&k)
	ans:=make([]int,n)
	for i,j:=n-k,0;i<n;i,j=i+1,j+2{
		ans[j]=i+1
	}
	num:=1
	for i:=n-1;i>=0;i--{
		if ans[i]==0{
			ans[i]=num
			num++
		}
	}
    for _,num:=range ans{
		Fprint(out,num," ")
	}
	defer out.Flush()
}

C++ 解法, 执行用时: 15ms, 内存消耗: 1024K, 提交时间: 2023-08-12 12:56:37

#include<iostream>

using namespace std;

int main()
{
	int n,m;cin>>n>>m;
	
	int l=1;
	for(int i=1;i<=m-1;i++)
	{
		cout<<l+1<<' '<<l<<' ';
		l+=2;
	}
	cout<<n<<' ';
	for(int i=l;i<n;i++) cout<<i<<' ';
}

Python3 解法, 执行用时: 477ms, 内存消耗: 9864K, 提交时间: 2023-08-12 12:56:06

n,k = map(int,input().split())
ans = list(range(1,n+1))
p = 2*k-2
for i in range(0,p,2):
    ans[i],ans[i+1] = ans[i+1],ans[i]
ans[p],ans[-1] = ans[-1],ans[p]
print(*ans)

上一题