音乐节拍

1122. 音乐节拍 (standard io)

时间限制: 1000 ms  空间限制: 262144 kb  具体限制  

题目描述

fj准备教他的奶牛弹奏一首歌曲，歌曲由n种音节组成，编号为1到n，而且一定按照从1到n的顺序进行弹奏，第i种音节持续b_i(1<=b_i<=10,000)个节拍，节拍从0开始计数，因此从节拍0到节拍b_1-1弹奏的是第1种音节，从b_1到b_1+b_2-1弹奏的是第2种音节，依此类推。
最近奶牛对弹琴不感兴趣了，他们感觉太枯燥了。所以为了保持奶牛们注意力集中，fj提出q个问题，问题的格式都是“第t次节拍弹奏的是哪种音节”
每个问题对应一个t_i请你帮奶牛来解决。

 

输入

第一行输入两个空格隔开的整数n和q。
第2至n+1行每行包含一个整数 b_i。
第n+2-n+q+1行每行包含一个整数t_i。

输出

输出有q行，每行输出对应问题的答案。

 

样例输入

3 5
2
1
3
2
3
4
0
1

样例输出

2
3
3
1
1

 

数据范围限制

n,q <= 50000

 

答案如下：↓↓↓

 

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<ctime>
 5 #include<algorithm>
 6 #include<cmath>
 7 using namespace std;
 8 #define debug(x) cerr<<#x<<'='<<x<<endl
 9 #define maxn 654321
10 
11 int n,q;
12 int a[maxn];
13 int s,y,l,v,a;
14 
15 void binary_chop(int low,int high,int y){
16     while (low<high){
17         int mid=(low+high)/2;
18         if (a[mid]>=y) high=mid;
19          else low=mid+1;
20     }
21     cout<<low<<endl;
22 }
23 int main(){
24     cin>>n>>q;
25     cin>>s;
26     a[1]=s-1;
27     for (int i=2;i<=n;i++){
28         scanf("%d",&s);
29         a[i]=s+a[i-1];
30     }
31     for (int j=1;j<=q;j++){
32         scanf("%d",&y);
33      binary_chop(1,n,y);
34     }    
35     return 0;
36 }
37     
38