题目链接

小红的环形数组

题目描述

小红拿到了一个大小为 的环形数组，她有 次询问。

每次查询会给定一个初始位置 pos（1-indexed），一个方向 dir（'L' 或 'R'），以及一个步数 k。

你需要计算从 pos 开始，按 dir 方向走 k 步后，最终落在哪个元素上。

解题思路

这是一个典型的环形数组问题，核心是利用模运算（Modulo Arithmetic）来处理“环绕”的边界情况。

1. 索引转换

题目中给定的位置是从 1 开始的（1-based），而编程中数组的索引通常是从 0 开始的（0-based）。因此，在进行计算前，我们需要将输入的 1-based 位置 pos 转换为 0-based 索引 start_idx：

2. 向右移动 ('R')

从 0-based 索引 start_idx 向右移动 步，新的索引是 start_idx + k。为了模拟环形，我们将结果对数组大小 取模。

3. 向左移动 ('L')

从 0-based 索引 start_idx 向左移动 步，新的索引是 start_idx - k。同样需要对 取模。

这里需要注意一个细节：在 C++ 和 Java 等语言中，对负数取模的结果可能是负数（例如 -1 % 5 的结果是 -1），这会导致数组越界。

为了保证结果始终是 [0, n-1] 范围内的非负整数，我们使用一个通用的技巧：先取模，再加上 ，再取模。

这个公式可以确保无论 start_idx - k 是正还是负，最终结果都是一个有效的 0-based 索引。

（在 Python 中，% 运算符的定义方式使得 (start_idx - k) % n 就能直接得到正确的结果，但使用上述通用公式也是完全正确的。）

4. 获取结果

计算出最终的 0-based 索引 final_idx 后，从数组中取出 a[final_idx] 的值即可。

代码

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    for (int i = 0; i < q; ++i) {
        int pos, k;
        char dir;
        cin >> pos >> dir >> k;

        // Convert to 0-based index
        int start_idx = pos - 1;
        int final_idx;

        if (dir == 'R') {
            final_idx = (start_idx + k) % n;
        } else { // dir == 'L'
            final_idx = ((start_idx - k) % n + n) % n;
        }

        cout << a[final_idx] << endl;
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int q = sc.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        for (int i = 0; i < q; i++) {
            int pos = sc.nextInt();
            String dir = sc.next();
            int k = sc.nextInt();

            // Convert to 0-based index
            int startIdx = pos - 1;
            int finalIdx;

            if (dir.equals("R")) {
                finalIdx = (startIdx + k) % n;
            } else { // dir.equals("L")
                finalIdx = ((startIdx - k) % n + n) % n;
            }

            System.out.println(a[finalIdx]);
        }
    }
}

import sys

def solve():
    try:
        n, q = map(int, sys.stdin.readline().split())
        a = list(map(int, sys.stdin.readline().split()))

        for _ in range(q):
            pos, dir, k_str = sys.stdin.readline().split()
            pos = int(pos)
            k = int(k_str)

            # Convert to 0-based index
            start_idx = pos - 1
            final_idx = 0

            if dir == 'R':
                final_idx = (start_idx + k) % n
            else:  # dir == 'L'
                # In Python, '%' with negative numbers works as expected mathematically
                # e.g., -1 % 5 is 4. So the +n trick is not strictly necessary.
                final_idx = (start_idx - k) % n
            
            print(a[final_idx])

    except (IOError, ValueError):
        return

solve()

算法及复杂度

  • 算法：模拟 / 模运算

  • 时间复杂度：。

    • 读取 个数组元素需要 的时间。
    • 处理 次查询，每次查询都是 的数学运算。

  • 空间复杂度：。

    • 需要 的空间来存储数组元素。