【Usaco 2009 Silver】JZOJ2020年9月19日提高B组T1 音乐节拍
2024-10-21 05:56:44
【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;
}
最新文章
- 不得不吐槽的Android PopupWindow的几个痛点(实现带箭头的上下文菜单遇到的坑)
- Mac上开启Web服务
- 高质量,高效率的多国语言软件开发(Web/PC/Mobile),使用接口约束/调用不同语言资源
- android手机两种方式获取IP地址
- Emag eht htiw Em Pleh 分类: POJ 2015-06-29 18:54 10人阅读 评论(0) 收藏
- CDH4.1基于Quorum-based Journaling的NameNode HA
- 关于text-align无法居中的问题
- struts2由&;lt;s:tree&;gt;要么dtree小工具 建立树
- STL__queue_的应用
- 尺取法 poj3061 poj3320
- MJRefresh 使用注意点
- 关于安卓手机的牛逼软件termux使用
- 初步学习大数据——设置虚拟机固定ip地址
- 如何方便的在windows测试python程序
- 线程 学习教程(一): Java中终止(销毁)线程的方法
- Python语言:下载上证股票数据程序
- nginx 了解一下
- The Golden Age CodeForces - 813B (数学+枚举)
- Retrofit/Okhttp API接口加固技术实践(上)
- Daubechies小波介绍
热门文章
- 通过一个很常用的场景来展示vue数据驱动的应用
- POJ 2432
- 20 HTTP1.0和HTTP1.1
- TCP 三次握手和四次挥手图解(有限状态机)
- CodeChef-RNDRATIO Mysterious Ratio 题解
- [MIT6.006] 7. Counting Sort, Radix Sort, Lower Bounds for Sorting 基数排序,基数排序,排序下界
- 92. Reverse Linked List II 翻转链表II
- [LeetCode题解]86. 分隔链表 | 三指针 + 虚拟头节点
- python笔记(1)---数据类型
- Python学习第三天 --- 分支、循环、条件、枚举