题解 P2969 【[USACO09DEC]音符Music Notes】

x_faraway_x · 2017-11-04 22:57:47 · 题解

STL的upper_bound函数，找到第一个大于待查元素的值，用法见代码。类似的还有lower_bound，找到的是第一个不小于待查元素的值。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=50005;
int b[N],sum[N],n,q;
inline int _read()
{
    int x=0; char c;
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0';
    return x;
}
int main()
{
    n=_read(),q=_read();
    for(int i=1;i<=n;i++)
    {
        b[i]=_read();
        sum[i]=sum[i-1]+b[i];
    }
    while(q--)
    {
        int x=_read();
        printf("%d\n",upper_bound(sum+1,sum+1+n,x)-sum);
    }
}