2026.1.26每日一题：音符

题目来源：https://ac.nowcoder.com/acm/problem/287777

定数960的一道题目，确实不难，核心在于二分查找和迭代器的基本语法。

思路很简单。对于每一个输入的 note 时长，我们可以用一个数组记录每一个 note 的截止时间。然后对于每次询问给出的时间，可以直接用内置函数 lower_bound 配合迭代器进行输出。注意的是截止时间的计算需要前缀和再减去 1。

主要强调一下的是代码优雅性。虽然我的代码不算优雅，但是输出答案部分我认为算是可以参考的。相比起直接手写二分然后返回查找的下标，内置的函数可以省下极大的代码量。 lower_bound 包括三个参数：开始位置，结束位置，查找目标值。核心特性大概就是：

• 功能：返回区间 [first, last) 中第一个满足 !(element < value) 的迭代器，即第一个不小于 value 的元素。
• 前提条件：区间必须按升序（或自定义规则）有序，否则结果未定义。
• 重载形式： lower_bound(first, last, value) —— 使用 operator< 比较。 lower_bound(first, last, value, comp) —— 使用自定义比较器 comp。

另外，通过迭代器相减，我们就可以得到能直接用 cout 输出的下标值。下面是 AC Code：

// LANG:C++
// Auther:Hanzhi

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef __int128 lll;

typedef pair<ll, ll> P;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, q;
    cin >> n >> q;
    vector<ll> note(n + 1);
    vector<ll> prd(n + 1);
    ll pre = 0;
    for (int i = 1; i <= n; i++) {
        cin >> note[i];
        prd[i] = pre + note[i] - 1;
        pre += note[i];
    }
    while (q--) {
        ll t;
        cin >> t;
        cout << lower_bound(prd.begin() + 1, prd.end(), t) - prd.begin() << endl;
    }
    return 0;
}