[BZOJ3412]&&[Usaco2009 Dec]Music Notes 乐谱

描述 Description

约翰准备教他的奶牛们弹一首歌. 这首歌由 N(l ≤ N ≤50000)个音阶组成，第 i 个音阶要敲击 Bi(l ≤ Bj ≤ 10000)次. 奶牛从第 0 时刻开始弹，因此他从 0 时刻到 B1-1 时刻都是敲第 1 个音阶，然后他从 B1 时刻到 B1+B2-1 时刻敲第 2 个音阶，从 B1+B2 时刻到 B1+B2+B3-1 时刻敲第 3 个音阶…… 现在有 Q( l ≤ Q ≤ 50000)个问题: 在时间段区间 [T,T+1) 内，奶牛敲的是哪个音阶?

看下面的一首歌， 第 1 个音阶持续 2 个单位时间，第 2 个音阶持续 1 个单位时间，第 3 个音阶持续 3 个单位时间.

以下是一些询问和回答：

<tbody>
    <tr>
        <th > 询问</th>
        <th > 回答的音阶</th>
    </tr>
    <tr>
        <td>2</td>
        <td>2</td>
    </tr>
    <tr>
        <td>3</td>
        <td>3</td>
    </tr>
    <tr>
        <td>4</td>
        <td>3</td>
    </tr>
    <tr>
        <td>0</td>
        <td>1</td>
    </tr>
    <tr>
        <td>1</td>
        <td>1</td>
    </tr>
</tbody>

输入格式 InputFormat

第 1 行：两个整数 N，Q.

第 2 到 N+1 行：第 i+l 行只有一个整数 Bi．

第 N+2 到 N+Q+I 行：第 N+i+l 行只有一个整数 Ti．

输出格式 OutputFormat

第 1 到 Q 行：对与每个询问，在词问的时间内，奶牛敲击的是哪个音阶？

样例输入 SampleInput

10 10
1
4
2
5
3
1
4
3
2
3
25
23
10
11
22
12
7
19
22
9

样例输出 SampleOutput

10
9
4
4
8
5
4
7
8
4

来源 Source

Silver

BZOJ 3412

代码 Code

前缀和记录，二分查找求答案。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
vector <int> sum;
int q;
int main()
{
    scanf("%d%d",&n,&q);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if (i>1) sum.push_back(sum.back()+x);
        else sum.push_back(x);
    }
    for (i=1;i<=q;i++)
    {
        scanf("%d",&x);
        printf("%d\n",upper_bound(sum.begin(),sum.end(),x)-sum.begin()+1);
    }
    return 0;
}