欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总贴：USACO历年白银组真题解析 | 汇总-CSDN博客
P2969 Music Notes
【题目来源】
洛谷：[P2969 USACO09DEC] Music Notes S - 洛谷
【题目描述】
FJ 准备教他的奶牛们演奏一首歌曲。这首歌由 \(N\) 个音符组成，其中第 \(i\) 个音符持续 \(B_i\) 个节拍（\(1 \leq N \leq 50,000\)，\(1 \leq B_i \leq 10,000\)），因此整首歌的长度不会超过 500,000,000 个节拍。奶牛们将在时间 0 开始演奏这首歌，因此它们将在时间 0 到时间 \(B_1\) 之前演奏第 1 个音符，在时间 \(B_1\) 到时间 \(B_1 + B_2\) 之前演奏第 2 个音符，依此类推。
然而，最近奶牛们对这首歌失去了兴趣，因为它们觉得这首歌太长且无聊。因此，为了确保奶牛们集中注意力，他向它们提出了 \(Q\) 个问题（\(1 \leq Q \leq 50,000\)），问题的形式为「在时间 \(T\) 到时间 \(T+1\) 之前的区间内，你应该演奏哪个音符？」奶牛们需要你的帮助来回答这些问题，这些问题以 \(T_i\) 的形式给出（\(0 \leq T_i \leq \text{end\_of\_song}\)）。
考虑这首由三个音符组成的歌曲，音符的持续时间分别为 2、1 和 3 个节拍：
Beat: 0 1 2 3 4 5 6 ...|----|----|----|----|----|----|--- ...1111111111 : :22222: :333333333333333:
这里有一组五个查询及其对应的答案：
Query Note
2 2
3 3
4 3
0 1
1 1
【输入】
* 第 1 行：两个用空格分隔的整数：\(N\) 和 \(Q\)
* 第 2 行到第 \(N+1\) 行：第 \(i+1\) 行包含一个整数：\(B_i\)
* 第 \(N+2\) 行到第 \(N+Q+1\) 行：第 \(N+i+1\) 行包含一个整数：\(T_i\)
【输出】
* 第 1 行到第 \(Q\) 行：对于每个查询，输出一个整数，表示奶牛们应该演奏的音符的索引。
【输入样例】
3 5
2
1
3
2
3
4
0
1
【输出样例】
2
3
3
1
1
【解题思路】
【算法标签】
《洛谷 P2969 Music Notes》 #排序# #前缀和# #USACO# #2009#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
int n, q, a[50005],b[50005];
int main()
{cin >> n >> q; // 输入n和qfor (int i=1; i<=n; i++) {int tmp;cin >> tmp;a[i] = a[i-1]+tmp; // 使用前缀和记录}for (int i=1; i<=q; i++) { // 记录q个问题cin >> b[i];}for (int i=1; i<=q; i++) { // 遍历q个问题int x = b[i];int l=1, r=n; // 二分搜索模板while (l<=r) { int mid = l + (r-l)/2;if (a[mid]<=x) { // 当mid对应的值小于等于xl = mid+1; // 左指针右移至mid+1} else r = mid-1; // 否则右指针左移至mid-1}cout << l << endl; // （输出什么感觉就是个玄学，正常先移动左指针，最后输出的就是r，这里输出l）}return 0;
}
【运行结果】
3 5
2
1
3
2
3
4
0
1
2
3
3
1
1