乐谱

【题目描述】
Farmer John准备教他的奶牛弹一首歌。这首歌由N个音阶组成，第i个音阶要弹Bi次。奶牛从第0时刻开始弹，因此她从第0时刻到第B1-1时刻都在弹第1个音阶，从第B1时刻到第B1+B2-1时刻都在弹第2个音阶……现在有Q个问题：在时刻[t,t+1]中，奶牛弹的是哪个音阶？
【输入格式】
第一行两个整数N，Q
接下来N行，第i+1行一个整数Bi
接下来Q行，每行一个整数t
【输出格式】
对于每个询问给出答案
【样例输入】
3 5
2
1
3
2
3
4
0
1
【样例输出】
2
3
3
1
1
【数据范围】
1<=N<=50000
1<=Bi<=10000
1<=Q<=50000
【分析】
二分查找。

var
  f,s:array[0..50001]of longint;
  i,x,n,q,t,l,r,mid:longint;
begin
  readln(n,q);
  s[0]:=0;
  for i:=1 to n do begin
    read(x);
      s[i]:=s[i-1]+x;
        f[i]:=s[i]-1;
  end;
  for i:=1 to q do begin
    readln(t);
    l:=1;r:=n;
      while l<=r do
      begin
            mid:=(l+r) div 2;
        if (t<=f[mid])and(t>=f[mid-1]+1) then break;
            if t>f[mid] then l:=mid+1 else r:=mid-1;
        end;
        writeln(mid);
  end;
end.