PAT乙级1008

佚名 4年前 (2020-01-12) 算法 1901人围观抢沙发百度已收录

1008 数组元素循环右移问题 (20分)

题目地址：https://pintia.cn/problem-sets/994805260223102976/problems/994805316250615808

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输入格式：

每个输入包含一个测试用例，第1行输入N（1≤N≤100）和M（≥0）；第2行输入N个整数，之间用空格分隔。

输出格式：

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

输入样例

6 2
1 2 3 4 5 6

输出样例

5 6 1 2 3 4

我的理解

出看题目，还在想移动数组位置，循环右移，即向右移动的过程中，超过数组边界的元素从元素左边补上。中间想着用临时变量保存被覆盖的元素，可是想着想着就出现了另外数组的身影、、、。可也正是题目的要求不允许使用另外的数组，可这该怎么办呢？灵机一动，其实没必要真的移动元素，只要表现起来像是移动了就可以了。稍微的“欺骗”一下计算机。只需要首先输出第n-m个元素到第n个元素，然后再输出第0个到第n-m个元素即可。

也可以将右移后的元素的新的下标和之前的下标做个映射。反正访问的时候进行处理就好了，表现出来就像是右移了。逻辑映射处理为 index += n - m 。

代码段

#include<iostream>
using namespace std;
int main() {
    int n = 0;
    int m = 0;
    cin >> n >> m;
    int number[n];
    for (int i = 0; i < n; i++) {
        cin >> number[i];
    }
    // 如果右移的量比较大，甚至发生了循环了一遍一遍又一遍，此时对右移的量进行处理，使其在一遍循环之内
    m %= n;
    for (int i = n - m; i < n; i++) {
        cout << number[i] << " ";
    }
    for (int i = 0; i < n - m; i++) {
        if (i != n - m - 1) {
            cout << number[i] << " ";   
        } else {
            cout << number[i];
        }
    }
    cout << endl;
    return 0;
}