【二分】-----【Music Notes S】

P2969 [USACO09DEC] Music Notes S

题目链接

题目描述

FJ 准备教他的奶牛们演奏一首歌曲。这首歌由 $N$ 个音符组成，其中第 $i$ 个音符持续 $B_i$ 个节拍（$1\le N\le 50,000$，$1\le B_i\le 10,000$），因此整首歌的长度不会超过 500,000,000 个节拍。奶牛们将在时间 0 开始演奏这首歌，因此它们将在时间 0 到时间 $B_1$ 之前演奏第 1 个音符，在时间 $B_1$ 到时间 $B_1+B_2$ 之前演奏第 2 个音符，依此类推。

然而，最近奶牛们对这首歌失去了兴趣，因为它们觉得这首歌太长且无聊。因此，为了确保奶牛们集中注意力，他向它们提出了 $Q$ 个问题（$1\le Q\le 50,000$），问题的形式为「在时间 $T$ 到时间 $T+1$ 之前的区间内，你应该演奏哪个音符？」奶牛们需要你的帮助来回答这些问题，这些问题以 $T_i$ 的形式给出（$0\le T_i\le \text{end\_of\_song}$）。

考虑这首由三个音符组成的歌曲，音符的持续时间分别为 2、1 和 3 个节拍：

Beat:   0    1    2    3    4    5    6    ...|----|----|----|----|----|----|--- ...1111111111     :              :22222:              :333333333333333:

这里有一组五个查询及其对应的答案：

Query    Note2        23        34        30        11        1

输入格式

* 第 1 行：两个用空格分隔的整数：$N$ 和 $Q$

* 第 2 行到第 $N+1$ 行：第 $i+1$ 行包含一个整数：$B_i$

* 第 $N+2$ 行到第 $N+Q+1$ 行：第 $N+i+1$ 行包含一个整数：$T_i$

输出格式

* 第 1 行到第 $Q$ 行：对于每个查询，输出一个整数，表示奶牛们应该演奏的音符的索引。

输入输出样例 #1

输入 #1

3 5 
2 
1 
3 
2 
3 
4 
0 
1

输出 #1

2 
3 
3 
1 
1

题解1（前缀和+手写二分）

一 、解题思路

1.前缀和建模

我们可以将每个音符所占的时间段看作一个区间：

• 第 $1$ 个音符对应时间区间为 $[0,B_1)$
• 第 $2$ 个音符对应时间区间为 $[B_1,B_1+B_2)$
• 第 $3$ 个音符对应时间区间为 $[B_1+B_2,B_1+B_2+B_3)$
• …

所以，我们可以维护一个前缀和数组 sum，其中：

sum[0] = 0
sum[i] = sum[i - 1] + B[i]

表示第 $i$ 个音符结束的时间点（不包含）。

2.查询模型转化

对于每个询问时间 $T$，我们需要找到第一个满足 sum[i] > T 的下标 i，也就是说 $T$ 落在第 i 个音符的时间区间 $[sum[i-1],sum[i])$ 中。

这是一个典型的有序数组中找第一个大于某值的位置的问题，可以使用手写二分解决。

---

四、完整代码：

#include<bits/stdc++.h>
using namespace std;int main()
{int n, q;cin >> n >> q;// nums[i] 表示第 i 个音符的持续节拍数，0号位占位（不使用）vector<int> nums(n + 1, 0);for (int i = 1; i <= n; i++){cin >> nums[i]; // 读入每个音符的持续时间}// 前缀和数组 sum[i] 表示前 i 个音符总共持续的节拍数// 即 sum[i] 表示第 i 个音符结束的时间（不包含）vector<int> sum(n + 1);for (int i = 1; i <= n; i++){sum[i] = sum[i - 1] + nums[i];}int a; // 用于接收每个查询时间 T_iwhile (q--){cin >> a;// 手写二分查找，找第一个满足 sum[mid] > a 的下标int l = 1, r = n;int ender = 0; // 记录答案（即对应的音符编号）while (l <= r){int mid = l + (r - l) / 2;if (sum[mid] > a){// 如果 sum[mid] > a，说明第 mid 个音符包含时间 a// 但是我们不能立刻返回 mid，因为还需要确保它是第一个满足条件的// 所以我们先记录答案，继续向左逼近ender = mid;r = mid - 1; // 继续在左半边查找}else{// 否则时间 a 还在 mid 之后的音符中l = mid + 1;}}// 输出结果（第几个音符）cout << ender << endl;}return 0;
}

---

五、复杂度分析

• 预处理前缀和：$O(n)$
• 每次查询使用二分：$O(logn)$，总共 $q$ 次查询
• 总时间复杂度：$O(n+qlogn)$，对于 $5\times 10^4$ 的数据规模完全可以接受

---

六、总结

1.本题本质上是一个典型的「查询区间在哪段区间中」的问题：

• 使用前缀和构造每个音符的结束时间
• 将每个查询转化为在有序数组中找第一个大于某值的位置
• 使用手写二分提高查询效率

2.这种技巧广泛应用于：

• 数轴上落点归属区间判断
• 前缀统计
• 排序 + 查询的经典模型

---

3.如需 STL 简洁写法，可以使用：

// 使用 upper_bound 在前缀和数组中查找第一个大于 t 的位置
// sum.begin() + 1：表示从 sum[1] 开始查找（sum[0] = 0 为占位）
// sum.end()：表示查找到 sum[n]（不含 sum[n+1]）
// t：目标时间，我们要找第一个满足 sum[i] > t 的 i
// 返回的是指针（迭代器），需要减去 sum.begin() 转换成下标
int idx = upper_bound(sum.begin() + 1, sum.end(), t) - sum.begin();  // 输出下标 idx，即时间 t 所在的音符编号（对应区间 [sum[idx - 1], sum[idx])）
cout << idx << endl;