小红的环形数组

[题目链接](https://www.nowcoder.com/practice/2094caa98e9c40fa8da8436ee7e232c6)

思路

给定一个长度为 $n$ 的环形数组（首尾相连），处理 $q$ 次查询：每次从位置 $p$ 出发，向左或向右走 $k$ 步，输出到达位置的元素值。

取模模拟

环形数组的核心在于用取模运算处理越界。将 1-indexed 的位置转换为 0-indexed 后：

向右走 $k$ 步：新下标 $= (p - 1 + k) \bmod n$
向左走 $k$ 步：新下标 $= ((p - 1 - k) \bmod n + n) \bmod n$

向左走时， $(p - 1 - k)$ 可能为负数，不同语言对负数取模的行为不同，因此先取模再加 $n$ 再取模，保证结果落在 $[0, n)$ 范围内。

注意 $k$ 可能很大，需要使用 64 位整数避免溢出。

样例演示

数组为 $[3, 4, 5, 2, 4]$ ， $n = 5$ 。

查询 1： $p = 1$ ，向右走 $3$ 步。

$ $\text{idx} = (1 - 1 + 3) \bmod 5 = 3$ $

$a[3] = 2$ ，输出 $2$ 。

查询 2： $p = 4$ ，向左走 $4$ 步。

$ $\text{idx} = ((4 - 1 - 4) \bmod 5 + 5) \bmod 5 = ((-1) \bmod 5 + 5) \bmod 5 = 4$ $

$a[4] = 4$ ，输出 $4$ 。

复杂度分析

时间复杂度： $O(n + q)$ ，读入数组 $O(n)$ ，每次查询 $O(1)$ 。
空间复杂度： $O(n)$ ，存储数组。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    while(q--){
        int p; char d; long long k;
        cin >> p >> d >> k;
        int idx;
        if(d == 'R'){
            idx = (int)(((long long)(p - 1) + k) % n);
        } else {
            idx = (int)((((long long)(p - 1) - k) % n + n) % n);
        }
        cout << a[idx] << "\n";
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());
        int[] a = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            st = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken());
            String d = st.nextToken();
            long k = Long.parseLong(st.nextToken());
            int idx;
            if (d.equals("R")) {
                idx = (int)(((long)(p - 1) + k) % n);
            } else {
                idx = (int)((((long)(p - 1) - k) % n + n) % n);
            }
            sb.append(a[idx]).append("\n");
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

n, q = map(int, input().split())
a = list(map(int, input().split()))
out = []
for _ in range(q):
    parts = input().split()
    p = int(parts[0])
    d = parts[1]
    k = int(parts[2])
    if d == 'R':
        idx = (p - 1 + k) % n
    else:
        idx = (p - 1 - k) % n
    out.append(str(a[idx]))
print('\n'.join(out))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const [n, q] = lines[0].split(' ').map(Number);
    const a = lines[1].split(' ').map(Number);
    const res = [];
    for (let i = 0; i < q; i++) {
        const parts = lines[2 + i].split(' ');
        const p = parseInt(parts[0]);
        const d = parts[1];
        const k = parseInt(parts[2]);
        let idx;
        if (d === 'R') {
            idx = (p - 1 + k) % n;
        } else {
            idx = (((p - 1 - k) % n) + n) % n;
        }
        res.push(a[idx]);
    }
    console.log(res.join('\n'));
});