题目： [USACO 2009 Dec S]Music Notes ，哈哈，我们今天来看一道有二分思想的题嘛，这是选自USACO上的一道题，好了，我们一起来看看题意吧：
题目描述是复制的，可能有部分显示不对，我就把题目链接放下面！
题目链接： [USACO 2009 Dec S]Music Notes
题目描述 FJ is going to teach his cows how to play a song、The song consists of N (1 <= N <= 50,000) notes, and the i-th note lasts for Bi (1 <= Bi <= 10,000) beats (thus no song is longer than 500,000,000 beats)、The cows will begin playing the song at time 0; thus, they will play note 1 from time 0 through just before time B1, note 2 from time B1 through just before time B1 + B2, etc、However, recently the cows have lost interest in the song, as they feel that it is too long and boring、Thus, to make sure his cows are paying attention, he asks them Q (1 <= Q <= 50,000) questions of the form, "In the interval from time T through just before time T+1, which note should you be playing?" The cows need your help to answer these questions which are supplied as Ti (0 <= Ti <= end_of_song)、 输入描述
Line 1: Two space-separated integers: N and QLines 2…N+1: Line i+1 contains the single integer: BiLines N+2…N+Q+1: Line N+i+1 contains a single integer: Ti 输出描述
Lines 1…Q: Line i of the output contains the result of query i as a single integer、
示例1
输入
3 5
2
1
3
2
3
4
0
1
输出
2
3
3
1
1
思路:
采用前缀和与二分的思想，很快就解决了
我们来看看成功AC的代码吧：
#includeusing namespace std;typedef long long ll;int n,q;int a[1000010];int sum[1000010];//存放前缀和的int main(){ ios::sync_with_stdio(false); cin>>n>>q; for(int i=1;i<=n;i++){ cin>>a[i]; sum[i]=sum[i-1]+a[i]; } while(q--){ int x; cin>>x; int ans=upper_bound(sum+1,sum+n+1,x)-sum;//这里减掉起始位置就是元素的下标了 cout< 谢谢你的阅读，由于作者水平有限，难免有不足之处，若读者发现问题，还请批评，在留言区留言或者私信告知，我一定会尽快修改的。若各位大佬有什么好的解法，或者有意义的解法都可以在评论区展示额，万分谢谢。
写作不易，望各位老板点点赞，加个关注!