题解 | #[USACO 2009 Dec S]Music Notes#

前缀和维护好音符时间求和数组，再去查找t时刻在前缀和数组中的最大插入位

置，查找用二分查找函数upper_bound()，时间复杂度O(Q*logN)

#include <bits/stdc++.h>
using namespace std;

const int Max = 50002;
int sum_B[Max];

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int N,Q;
    cin>>N>>Q;
    for(int i = 1;i <= N;i++)
        cin>>sum_B[i];
    for(int i = 2;i <= N;i++)    //前缀和
        sum_B[i] += sum_B[i-1];
    
    for(int i = 1;i <= Q;i++){
        int q;
        cin>>q;
        cout<<upper_bound(sum_B+1, sum_B+N+1, q) - sum_B;
        cout<<'\n';
    }
    return 0;
}