💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🍥 本次总体来说是非常简单的，应该是人均AK的水准啦

1️⃣ 简单构造题

2️⃣ 模拟题，看起来不是很能暴力，其实就是暴力

🎤 01.LYA的魔法排序

问题描述

在魔法世界中，LYA 是一位著名的魔法师。她最近发明了一种特殊的魔法排序术，可以将 个不同的魔法物品排列成一行。这种排序术有一个独特的特性：恰好有 对相邻的物品，前一个物品的魔力值大于后一个物品的魔力值。

LYA 想要展示她的魔法排序术，但她需要你的帮助来确定物品的具体排列顺序。你能协助她完成这个任务吗？

输入格式

输入包含一行，有两个用空格分隔的正整数 和 。

• 表示魔法物品的数量。
• 表示相邻物品魔力值逆序的对数。

输出格式

输出一行，包含 个用空格分隔的正整数，表示魔法物品的排列顺序。每个数字代表物品的魔力值，范围从 到 ，每个数字只能使用一次。

如果有多种可能的排列方式，输出任意一种即可。

样例输入

5 2

样例输出

1 4 2 5 3

数据范围

题解

来分析下这个问题：

我们需要构造一个长度为 的排列，其中恰好有 对相邻的数满足前一个数大于后一个数。

1. 观察发现，如果我们将前 个数按降序排列，后面的数按升序排列，就可以恰好得到 对逆序对。
2. 可以这样构造：
   • 先放置数字
   • 然后放置数字
3. 构造完之后：
   • 前 个数中，每相邻两个数都构成一个逆序对，共 个。
   • 而 和 是升序的，不构成逆序对。
   • 后面的数字都是升序的，也不构成逆序对

参考代码

• Python

# 读取输入
n, k = map(int, input().split())

# 构造魔法排序
result = []

# 先添加前k+1个数，降序排列
for i in range(k + 1, 0, -1):
    result.append(i)

# 再添加剩下的数，升序排列
for i in range(k + 2, n + 1):
    result.append(i)

# 输出结果
print(' '.join(map(str, result)))

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        
        // 构造魔法排序
        StringBuilder result = new StringBuilder();
        
        // 先添加前k+1个数，降序排列
        for (int i = k + 1; i > 0; i--) {
            result.append(i).append(" ");
        }
        
        // 再添加剩下的数，升序排列
        for (int i = k + 2; i <= n; i++) {
            result.append(i).append(" ");
        }
        
        // 输出结果
        System.out.println(result.toString().trim());
        
        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, k;
    
    // 读取输入
    cin >> n >> k;
    
    vector<int> result;