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

//使用前缀和记录在什么时候音符开始演奏，然后在通过二分查找值的范围即可。
#include <bits/stdc++.h>


using namespace std;
const int maxn = 50000+10;
int N, Q;
int ying_fu[maxn];

int find_pos(int x) {
    int l = 1, r = N;
    while (l<r) {
        int mid = (l+r)/2;
        if (ying_fu[mid]>=x) r = mid;
        else l = mid+1;
    }
    return l;
}

int main() {
    int k;
    cin>>N>>Q;
    //计算前缀和
    for (int i=1;i<=N;i++) {
        ying_fu[i] = ying_fu[i-1];
        scanf("%d", &k);
        ying_fu[i] += k;
    }
    while (Q--) {
        scanf("%d", &k);
        int pos = find_pos(k);
        if (ying_fu[pos]==k) pos++;
        printf("%d\n", pos);
    }
    
    return 0;
}