[USACO 2009 Dec S]Music Notes
二分板子, 写的不太熟练 也可以直接使用upper_bound()
ac代码:

//寻找第一个大于前缀和的下标+1
//2(0 1) 3(2) 6(3 4 5)
#include <bits/stdc++.h>
using namespace std;
int num[50005];
int n ,q;

int found_first_bigger(int x)
{
    int i = 0, j = n-1;
    //1 2 2 3 4 5 6 7
    int mid;
    while(i<j)
    {
        mid = (i+j)/2;
        if(num[mid]>x)//不是mid>x
        {
            j = mid;
        }
        else//mid<=x
        {
            i = mid+1;
        }
    }
    return i;
}

int main()
{
    cin>>n>>q;
    cin>>num[0];
    for(int i = 1; i<n; i++)
    {
        cin>>num[i];
        num[i]+=num[i-1];
    }
    int temp;
    for(int i = 0; i<q; i++)
    {
        cin>>temp;
        cout<< found_first_bigger(temp) +1<<'\n';
        //cout<< upper_bound(num , num+n, temp) - num +1<<'\n';
    }
    return 0;
}