题目分析

解决这种数组元素移位问题的一个常用算法是翻转法。

对具有n个元素的数组进行m位右移，数组元素位置从(a₀, ··· a_n-m-1, a_n-m a_n-1)变化为(a_n-m ··· a_n-1, a₀, a_n-m-1)。可将数组元素分为两部分，前半部分从a₀到a_n-m-1，后半部分从a_n-m到a_n-1，观察发现实际上完成的是前半部分和后半部分的整体位置互换。线性代数矩阵运算中，从AB向BA转化，我们可以借助转置运算来完成：(A^TB^T)^T=BA，这对于解决这个问题有借鉴意义。

类似的，我们可以设置一个翻转函数，其功能为将给定数组的某一部分进行逆序翻转。这样通过三次部分和整体的逆序翻转，我们就能够得到移位后的数组。这一方法完全满足题目对于不使用额外数组和移动数据次数尽量少的要求。

代码

#include "iostream"
#define maxn 105
using namespace std;

void reverse(int a[], int begin, int end){
    int tmp = 0;
    while(begin < end){
        tmp = a[end];
        a[end] = a[begin];
        a[begin] = tmp;
        begin++, end--;
    }
}

int main(){
    int n, m, num[maxn];
    cin >> n >> m;
    m = m % n;       // 针对m>n的情况
    for(int i=0; i<n; ++i)
        cin >> num[i];
    reverse(num, 0, n-m-1);
    reverse(num, n-m, n-1);
    reverse(num, 0, n-1);
    bool first = true;
    for(int i=0; i<n; ++i)
        if(first){
            cout << num[i];
            first = false;
        }
        else
            cout << " " << num[i];
    return 0;
}

踩坑指南

一个隐藏点是n和m的取值大小问题。当m取值大于n的时候，如果不进行特殊处理，会出现数组访问溢出的情况。因此程序中在读入n和m后，索性强制对m进行以n为除数的取余操作，这样可以保证无论m和n的大小关系如何都不会导致数组访问越界。