PAT乙级1008

题目链接

https://pintia.cn/problem-sets/994805260223102976/problems/994805316250615808

---

查了查网上的题解，情况如下：

• 一种方法是和我（题解一）一样的

• 这个方法真的奇葩，并不交换数组元素位置，只是根据n和m改变输出顺序，我个人觉得不可取

  参考链接：https://blog.csdn.net/qq_35283188/article/details/77370798

• 这种方法应该是最符合题目要求的，三次逆置法（题解二），感觉很像上学期算法设计与分析考试里的一道题。

  参考链接：https://www.cnblogs.com/cdp1591652208/p/7161684.html

• 还有一个方法，看起来挺玄乎的，没看懂就没怎么看

  参考链接：https://blog.csdn.net/qq_22194315/article/details/52625679

题解一

我这个方法应该是移了n+m次，看起来只用了一个数组，其实也是用了两个数组吧……惭愧惭愧

// PAT BasicLevel 1008
// https://pintia.cn/problem-sets/994805260223102976/problems/994805316250615808

#include <iostream>
using namespace std;

int main()
{
    // 获取用户输入的n和m以及n个整数
    int n,m;
    int arr[200];
    cin >> n >> m;
    for(int i=0;i<n;i++){
        cin >> arr[i];
    }

    // m==0则不用移动
    if(m>0){
        // 假如有10个数，右移13位其实相当于13%10=3位。
        // 所以m一定小于n，所以把数组大小定义为200
        m = m % n;

        // 整体右移m位
        for(int i=n-1;i>=0;i--){
            arr[i+m]=arr[i];
        }

        // 把最右侧的m个数字循环右移到左侧
        for (int i = n-1; i < n + m;i++){
            arr[i%n]=arr[i];
        }
    }


    // 输出结果
    cout << arr[0];
    for(int i=1;i<n;i++){
        cout << ' ' << arr[i]; 
    }

    //system("pause");
    return 0;
}

题解二

这道题的参考链接里说这是链表，讲错了吧，这儿哪有链表……核心在于三次逆置

但时间（3ms）与内存占用（400KB左右）和题解一差不多，可能测试用例输入规模不够大吧。

// PAT BasicLevel 1008
// httarrs://arrintia.cn/arrroblem-sets/994805260223102976/arrroblems/994805316250615808

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    // 获取用户输入的n和m以及n个整数
    int n,m;
    cin >> n >> m;
    int* arr=new int[n];
    for(int i=0;i<n;i++){
        cin >> arr[i];
    }

    // m==0则不用移动
    if(m>0){
        // 假如有10个数，右移13位其实相当于13%10=3位。
        // 所以m一定小于n，所以把数组大小定义为200
        m = m % n;

        // 三次逆置
        reverse(arr, arr + n - m);
        reverse(arr + n - m, arr + n);
        reverse(arr, arr + n);
    }


    // 输出结果
    cout << arr[0];
    for(int i=1;i<n;i++){
        cout << ' ' << arr[i]; 
    }

    //system("pause");

    delete[] arr;
    return 0;
}

---

作者：@臭咸鱼

转载请注明出处：https://chouxianyu.github.io

欢迎讨论和交流!

---