1008. 数组元素循环右移问题.md

【PAT B-1008】数组元素循环右移问题

题意概述

一个数组 A 中存有 N 个整数，在不允许使用另外数组的前提下，将每个整数循环向右移 M 个位置，即将 A 中的数据由$A_0A_1\cdots A_{N-1}$变换为$A_{N-M}\cdots A_{N-1}A_0A_1\cdots A_{N-M-1}$（最后 M 个数循环移至最前面的 M 个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

输入输出格式

输入第 1 行给出两个整数 N 和 M；第 2 行输入 N 个整数，之间用空格分隔。

在一行中输出循环右移 M 位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。

数据规模

$$1<=N<=100,M>=0$$

算法设计

3 次翻转即可。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni, mi;
    cin >> ni >> mi;
    vector<gg> v(ni);
    for (gg& i : v) {
        cin >> i;
    }
    mi = ni - mi % ni;
    reverse(v.begin(), v.begin() + mi);
    reverse(v.begin() + mi, v.end());
    reverse(v.begin(), v.end());
    for (gg i = 0; i < v.size(); ++i) {
        cout << v[i] << (i == v.size() - 1 ? "\n" : " ");
    }
    return 0;
}