当前位置：首页 > ops >正文

2025.05.22-得物春招机考真题解析-第二题

ops 2025/7/27 21:33:02

📌 点击直达笔试专栏 👉《大厂笔试突围》

💻 春秋招笔试突围在线OJ 👉 笔试突围OJ

02. 魔法书页重排

问题描述

A先生是一位魔法师，他有一本古老的魔法书，书中有 $n$ 页，每页都刻有一个魔法符号。最初，第 $i$ 页上刻着数字 $i$ 。

现在A先生需要按照古老的仪式来重新排列这些魔法符号。仪式的规则是：按照从小到大的顺序，对于每个 $[1, n]$ 之间的整数 $x$ ，将所有页码为 $x$ 的倍数的页面上的魔法符号向右循环移动一位。

具体来说，如果有 $k$ 个页面的页码是 $x$ 的倍数，分别为 $p_1, p_2, \ldots, p_k$ （按页码从小到大排列），那么这些页面上的魔法符号会按如下方式移动： $p_k$ 页的符号移动到 $p_1$ 页， $p_1$ 页的符号移动到 $p_2$ 页，以此类推。

请输出仪式完成后每页上的魔法符号是什么。

输入格式

第一行包含一个正整数 $n$ （ $\leq n \leq 10^5$ ），表示魔法书的页数。

输出格式

第一行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 页上的魔法符号。

样例输入

样例输出

5 3 2 1 4

8 7 3 5 4 2 6 1

数据范围

$\leq n \leq 10^5$

样例	解释说明
样例1	初始状态：[1,2,3,4,5]。x=1时，所有页面循环右移：[5,1,2,3,4]。x=2时，页面2,4循环右移：[5,3,2,1,4]。x=3时，页面3循环右移：不变。x=4,5同理
样例2	按照相同规则进行多轮循环移动操作

题解

这道题的关键是理解"循环右移"的概念，以及如何高效地模拟这个过程。

算法思路：

初始化数组 $A [i] = i$
对于每个 $x$ 从 $1$ 到 $n$ ，找出所有 $x$ 的倍数位置
将这些位置上的数值进行循环右移

具体实现：

对于每个 $x$ ，收集所有倍数位置： $\ldots$
如果只有一个位置，则无需移动
否则，保存最后一个位置的值，然后从后往前依次移动

举例说明（ $n = 5$ ）：

初始： $[1, 2, 3, 4, 5]$
$x = 1$ ：位置 $[1, 2, 3, 4, 5]$ 循环右移 → $[5, 1, 2, 3, 4]$
$x = 2$ ：位置 $[2, 4]$ 循环右移 → $[5, 3, 2, 1, 4]$
$x = 3, 4, 5$ ：只有一个位置，无需移动

时间复杂度分析：对于每个 $x$ ，需要遍历其所有倍数，总的时间复杂度为 $\log n)$ ，因为 $\sum_{x=1}^{n} \lfloor \frac{n}{x} \rfloor = O(n \log n)$ 。

参考代码

Python

import sys
input = lambda: sys.stdin.readline().strip()n = int(input())
a = [0] + list(range(1, n + 1))  # 1-indexed数组for x in range(1, n + 1):pos = []  # 存储x的倍数位置for j in range(x, n + 1, x):pos.append(j)if len(pos) <= 1:continue# 循环右移：最后一个元素移到第一个位置last_val = a[pos[-1]]for i in range(len(pos) - 1, 0, -1):a[pos[i]] = a[pos[i - 1]]a[pos[0]] = last_val# 输出结果（去掉第0个元素）
print(' '.join(map(str, a[1:])))

#include <iostream>
#include <vector>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i++) {a[i] = i;  // 初始化}for (int x = 1; x <= n; x++) {vector<int> pos;  // 存储x的倍数位置for (int j = x; j <= n; j += x) {pos.push_back(j);}if (pos.size() <= 1) continue;// 循环右移int last_val = a[pos.back()];for (int i = pos.size() - 1; i > 0; i--) {a[pos[i]] = a[pos[i - 1]];}a[pos[0]] = last_val;}for (int i = 1; i <= n; i++) {cout << a[i];if (i < n) cout << " ";}cout << "\n";return 0;
}

Java

import java.util.*;
import java.io.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));PrintWriter pw = new PrintWriter(System.out);int n = Integer.parseInt(br.readLine());int[] a = new int[n + 1];// 初始化数组for (int i = 1; i <= n; i++) {a[i] = i;}for (int x = 1; x <= n; x++) {List<Integer> pos = new ArrayList<>();// 收集x的倍数位置for (int j = x; j <= n; j += x) {pos.add(j);}if (pos.size() <= 1) continue;// 循环右移操作int lastVal = a[pos.get(pos.size() - 1)];for (int i = pos.size() - 1; i > 0; i--) {a[pos.get(i)] = a[pos.get(i - 1)];}a[pos.get(0)] = lastVal;}for (int i = 1; i <= n; i++) {pw.print(a[i]);if (i < n) pw.print(" ");}pw.println();pw.close();br.close();}
}