题目链接

音符

题目描述

一首歌由 个音符组成，第 个音符持续 拍。音符按顺序演奏，从时刻 开始。例如，第一个音符的演奏区间是 ，第二个音符的演奏区间是 ，以此类推。

现在有 次询问，每次询问给出一个时刻 ，你需要输出该时刻正在演奏的是第几个音符。

解题思路

本题的核心是根据给定的时间点，快速定位其所属的音符区间。如果对每次查询都线性扫描所有音符来累加时长，总时间复杂度会达到 ，可能会超时。

为了优化查询过程，我们可以预处理数据。一个有效的方法是使用前缀和。我们创建一个前缀和数组 ，其中 记录前 个音符的总时长。

根据这个定义，第 个音符（ 从 1 开始）的演奏时间区间为 。

对于一个查询时刻 ，我们要找到一个索引 ，使得 。这个条件等价于寻找第一个使得 成立的索引 。

由于所有音符的持续时间 都是正数，所以前缀和数组 是一个严格单调递增的序列。这使得我们可以利用二分查找来高效地找到这个索引 。

具体来说，我们可以在前缀和数组上执行 upper_bound 操作。upper_bound(T_j) 会找到数组中第一个值严格大于 的元素。该元素在（从1开始计数的）音符序列中的编号，就是我们要求的答案。

算法步骤：

  1. 读入 和 。
  2. 读入 个音符的持续时间，并构建一个长度为 的前缀和数组 。
  3. 对于 次查询，每次读入一个时刻 。
  4. 在 数组上使用二分查找，找到第一个大于 的元素的索引，并输出该索引。

代码

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

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

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

    vector<long long> prefix_sum(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        long long duration;
        cin >> duration;
        prefix_sum[i] = prefix_sum[i - 1] + duration;
    }

    for (int i = 0; i < q; ++i) {
        long long t;
        cin >> t;
        // 寻找第一个大于 t 的元素的迭代器
        auto it = upper_bound(prefix_sum.begin() + 1, prefix_sum.end(), t);
        // 计算该迭代器对应的音符编号（从1开始）
        cout << distance(prefix_sum.begin(), it) << 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();

        long[] prefixSum = new long[n + 1];
        prefixSum[0] = 0;
        for (int i = 1; i <= n; i++) {
            prefixSum[i] = prefixSum[i - 1] + sc.nextInt();
        }

        for (int i = 0; i < q; i++) {
            long t = sc.nextLong();
            int noteIndex = upperBound(prefixSum, t);
            System.out.println(noteIndex);
        }
    }

    // 寻找数组中第一个大于 target 的元素的索引
    private static int upperBound(long[] arr, long target) {
        int left = 1; // 从音符1开始查找
        int right = arr.length;
        int ans = arr.length; // 如果没找到，说明在最后一个音符之后，但题目保证在范围内

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > target) {
                ans = mid;
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

import bisect

def main():
    n, q = map(int, input().split())
    durations = list(map(int, input().split()))
    queries = list(map(int, input().split()))

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

    for t in queries:
        # bisect_right 寻找第一个 > t 的元素的位置（0-indexed）
        # 结果加 1 转换为 1-indexed 的音符编号
        ans = bisect.bisect_right(prefix_sum, t) + 1
        print(ans)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：前缀和 + 二分查找。
  • 时间复杂度：。其中 是构建前缀和数组的时间开销， 是处理 次查询的总时间开销，每次二分查找需要 。
  • 空间复杂度：，用于存储前缀和数组。