【题目来源】
学而思编程：数组旋转
【题目描述】
给定一个整数数组 \(a_1,a_2,⋯ ,a_n\)，然后输入一系列数字 \(x_1,x_2,⋯ ,x_m\)，如果 \(x_i>0\)，代表将数组中的元素向右旋转 \(x_i\) 个位置（例如，\(1,2,3,4,5\) 向右旋转 \(2\) 个位置将变成 \(4,5,1,2,3\)）。如果 \(x_i<0\)，代表将数组中的元素向左旋转 \(−x_i\) 个位置（例如，\(x_i=−3\) 时，\(1,2,3,4,5\) 向左旋转 \(3\) 个位置将变成 \(4,5,1,2,3\)）。
【输入】
输入第一行一个整数 \(n\)，表示数组的元素个数。
第二行 \(n\) 个空格分隔的整数，表示数组 \(a_i\)。
第三行一个整数 \(m\)，表示旋转次数。
第二行 \(m\) 个空格分隔的整数，表示每次旋转的位置\(x_i\)。
【输出】
输出 \(m\) 行，第 \(i\) 行输出 \(n\) 个空格分隔的整数，表示第 \(i\) 次旋转后的数组情况。
【输入样例】
7
1 3 5 7 2 4 6
5
0 1 -2 3 -4
【输出样例】
1 3 5 7 2 4 6
6 1 3 5 7 2 4
3 5 7 2 4 6 1
4 6 1 3 5 7 2
5 7 2 4 6 1 3
【核心思想】
-
问题描述：给定长度为 \(n\) 的数组 \(a\)，执行 \(m\) 次旋转操作（\(x_i > 0\) 向右旋转 \(x_i\) 位，\(x_i < 0\) 向左旋转 \(-x_i\) 位），每次操作后输出当前数组。这是一个模拟问题，核心在于用偏移量避免实际移动数组元素，\(O(1)\) 完成每次旋转。
-
算法选择：
- 偏移量追踪：维护一个偏移量 \(p\)，表示数组逻辑上的起始位置相对于物理存储的偏移
- 模运算：所有操作转化为偏移量的加减，对 \(n\) 取模
-
关键步骤：
- 初始化：读取 \(n\)、数组 \(a[0..n-1]\)、\(m\)
- 偏移量初始化：\(p = 0\)（逻辑起始位置为物理位置 \(0\)）
- 处理每次旋转（\(m\) 次）：
- 读取 \(x\)
- 更新偏移量：\(p -= x\)（向右旋转 \(x\) 位等价于逻辑起始位置左移 \(x\) 位，即 \(p\) 减 \(x\)）
- 取模规范化：\(p = p \% n\)（控制偏移量在 \([-n+1, n-1]\) 范围内）
- 输出数组：遍历 \(i = 0\) 到 \(n-1\)，输出 \(a[(i + p + n) \% n]\)（\(+n\) 再取模处理负数）
- 注意：向右旋转 \(x\) 位（如 \(1,2,3,4,5 \to 4,5,1,2,3\)）等价于逻辑起始位置从 \(0\) 变为 \(n-x\)，即 \(p = -x\)
-
时间/空间复杂度：
- 时间复杂度：\(O(n \times m)\)，每次输出 \(n\) 个元素
- 空间复杂度：\(O(n)\)，原数组存储
-
模拟的核心思想：
- 虚拟索引：不实际移动数组元素，而是通过偏移量计算逻辑位置到物理位置的映射
- 模运算优雅处理环形：\(p\) 的更新和查询都通过对 \(n\) 取模实现，天然支持左右旋转的统一处理
- 负数处理：\(+n\) 后再取模确保索引始终非负
- 适用于数组旋转、环形缓冲区、循环队列类问题
【算法标签】
模拟
【代码详解】
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int a[N]; // 存储数组
int n, m; // n: 数组长度，m: 操作次数
int main()
{cin >> n; // 输入数组长度for (int i = 0; i < n; i++) // 输入数组元素cin >> a[i];cin >> m; // 输入操作次数int p = 0; // 偏移量，表示当前数组相对于原始数组的偏移while (m--) // 处理每次操作{int x; // 操作数cin >> x; // 输入操作数p -= x; // 更新偏移量p %= n; // 取模，防止偏移量过大for (int i = 0; i < n; i++) // 输出数组cout << a[(i + p + n) % n] << " "; // 通过偏移量计算实际位置cout << endl; // 换行}return 0;
}
【运行结果】
7
1 3 5 7 2 4 6
5
0 1 -2 3 -4
1 3 5 7 2 4 6
6 1 3 5 7 2 4
3 5 7 2 4 6 1
4 6 1 3 5 7 2
5 7 2 4 6 1 3