思路: 前缀和+二分

因为可能会走很多圈，我们只考虑最后一圈。

如果对于最后一圈，不再走了，那么就说明我们最后到达的点是 $1$ 号点

否则我们二分来考虑我们走完这些时间到达了哪个点，如果还在路上，就是出发点，如果到达某个点 $A$，则答案就是 $A$ 。

时间复杂度：$O(n\log n)$

代码

C++

#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> t(n);
    for (int i = 0; i < n; i++) {
        cin >> t[i];
    }

    vector<int> pre(n + 1);
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + t[i - 1];
    }

    while (Q > 0) {
        Q--;

        int x;
        cin >> x;
        x %= pre[n];

        if (x == 0) {
            cout << "1\n";
            continue;
        }

        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (pre[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        if (pre[l] > x) {
            l -= 1;
        }

        cout << l + 1 << "\n";
    }

    return 0;
}

Python

n, Q = map(int, input().split())
t = list(map(int, input().split()))

pre = [0] * (n + 1)
for i in range(1, n + 1):
    pre[i] = pre[i - 1] + t[i - 1]

while Q > 0:
    Q -= 1

    x = int(input())
    # 去掉走的每个圈，只看最后一轮
    x %= pre[-1]

    # 如果不走了，说明停在了 1 号点
    if x == 0:
        print("1")
        continue

    # 找到大于等于 x 的最小值
    l, r = 0, n
    while l < r:
        mid = (l + r) >> 1
        if pre[mid] >= x:
            r = mid
        else:
            l = mid + 1

    # 如果恰好等于 x ，说明恰好从 l 走到了 l + 1
    if pre[l] > x:
        l -= 1

    print(l + 1)

Java

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int Q = scanner.nextInt();

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

        int[] pre = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            pre[i] = pre[i - 1] + t[i - 1];
        }

        while (Q > 0) {
            Q--;

            int x = scanner.nextInt();
            x %= pre[n];

            if (x == 0) {
                System.out.println("1");
                continue;
            }

            int l = 0, r = n;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (pre[mid] >= x) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }

            if (pre[l] > x) {
                l -= 1;
            }

            System.out.println(l + 1);
        }
    }
}

题目描述

大家都知道，地球是圆的。小红想要效仿麦哲伦，进行环球航行。

已知地球上一共有 $n$ 个点。小红从 $1$ 号点出发的到达地为 $2$ 号点，从 $i$ 号点出发，到达的下一站是 $i+1$ 号点，耗费的时间为 $t_i$ 。如果从 $n$ 号点出发，到达的下一站是 $1$ 号点。

现在，小红环球航行了很久，已经非常疲惫了，作为他的助理，请你告诉他最近一次待过的点是哪个点。

小红的环球航行从 $1$ 号点出发。

输入描述

第一行，两个数 $n(1\leq n\leq 10^5)$ 和 $Q(1\leq Q\leq 10^5)$，表示地球上的点数，以及询问次数。

第二行，$n$ 个数 $t_1,t_2，..,t_n$，$t_i(1\leq t_i\leq 10^4)$ 表示从 $i$ 号点到 $i+1$ 号点的航行时间。

接下来 $Q$ 行，每行一个整数 $t(1\leq t\leq 10^9)$ ，表示询问的时间。

输出描述

输出 $Q$ 行，每行一个数，表示在小红航行时间为 $t$ 时，最近一次待过的点

样例

输入

6 4
1 1 4 5 1 4
5 
11
15
20

输出

3
5
6
3

说明

航行时间为 $5$ 时，还在从 $3$ 号点到 $4$ 号点的路上，所以最近一次待过的点为 $3$ 号点

航行时间为 $11$ 时，从 $4$ 号点到 $5$ 号点出发，到达了 $5$ 号点，所以最近一次待过的点为 $5$ 号点

航行时间为 $15$ 时，还在从 $6$ 号点到 $1$ 号点的路上，所以最近一次待过的点为 $6$ 号点

航行时间为 $20$ 时，已经到达过所有点一次，现在是第二圈了，当前是从 $3$ 号点到 $4$ 号点的路上，所以最近一次待过的点为 $3$ 号点 .