【Usaco 2009 Silver】JZOJ2020年9月19日提高B组T1 音乐节拍

题目

Description

FJ准备教他的奶牛弹奏一首歌曲，歌曲由N(1<=N<=50,000)种音节组成，编号为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(1<=Q<=50,000)个问题，问题的格式都是“第T次节拍弹奏的是哪种音节”

每个问题对应一个T_i(0<=T_i<=节拍总数-1)请你帮奶牛来解决。

Input

第一行输入两个空格隔开的整数N和Q

第2至N+1行每行包含一个整数 B_i

第N+2-N+Q_1行每行包含一个整数T_i

Output

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

Sample Input

3 5

2

1

3

2

3

4

0

1

Sample Output

2

3

3

1

1

题解

题意

给出\(n\)个音节的持续节拍时间

问第\(x\)节拍时是哪个音节

多组询问

分析

容易想到二分

统计\(B_i\)的前缀和，记为\(S_i\)

询问第\(x\)节拍就是找出最右的小于\(x\)的\(S_i\)

输出\(i+1\)即可

比赛总结

对于这种明显的签到题，一定要打对拍，以防一不小心打错导致签到题白给

Code

#include<bits/stdc++.h>

using namespace std;

int n,q,x,l,r,mid,ans,a[50005];

int read()

{

	int res=0;char ch=getchar();

	while (ch<'0'||ch>'9') ch=getchar();

	while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch-'0'),ch=getchar();

	return res;

}

int main()

{

	freopen("mnotes.in","r",stdin);

	freopen("mnotes.out","w",stdout);

	n=read();q=read();

	for (int i=1;i<=n;++i)

		a[i]=read(),a[i]+=a[i-1];

	for (int i=1;i<=q;++i)

	{

		x=read();++x;

		l=1;

		r=n;

		ans=0;

		while (l<=r)

		{

			mid=(l+r)>>1;

			if (a[mid]<x)

			{

				l=mid+1;

				ans=mid;

			}

			else r=mid-1;

		}

		printf("%d\n",ans+1);

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}