【题目描述】 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.转载于:https://www.cnblogs.com/JRX2015U43/p/6533538.html
