NC24866 [USACO 2009 Dec S]Music Notes
NC24866 [USACO 2009 Dec S]Music Notes
题目
题目描述
FJ is going to teach his cows how to play a song. The song consists of N (1 <= N <= 50,000) notes, and the i-th note lasts for Bi (1 <= Bi <= 10,000) beats (thus no song is longer than 500,000,000 beats). The cows will begin playing the song at time 0; thus, they will play note 1 from time 0 through just before time B1, note 2 from time B1 through just before time B1 + B2, etc.
However, recently the cows have lost interest in the song, as they feel that it is too long and boring. Thus, to make sure his cows are paying attention, he asks them Q (1 <= Q <= 50,000) questions of the form, "In the interval from time T through just before time T+1, which note should you be playing?" The cows need your help to answer these questions which are supplied as Ti (0 <= Ti <= end_of_song).
Consider this song with three notes of durations 2, 1, and 3 beats:
Beat: 0 1 2 3 4 5 6 ...
|----|----|----|----|----|----|--- ...
1111111111 : :
22222: :
333333333333333:
Here is a set of five queries along with the resulting answer:
Query Note
2 2
3 3
4 3
0 1
1 1
输入描述
* Line 1: Two space-separated integers: N and Q
* Lines 2..N+1: Line i+1 contains the single integer: Bi
* Lines N+2..N+Q+1: Line N+i+1 contains a single integer: Ti
输出描述
* Lines 1..Q: Line i of the output contains the result of query i as a single integer.
示例1
输入
3 5
2
1
3
2
3
4
0
1
输出
2
3
3
1
1
题解
思路
知识点:二分。
先做前缀和得到每个音符的终止位置,发现音符 \(i\) 出现在 \([sum_{i-1},sum_{i})\) 。要查找 \([T,T+1)\) 区间的音符,于是二分查找第一个位置 \(i\) 使得 \(sum_i>T\) ,就有 \([T,T+1) \subseteq [sum_{i-1},sum_{i})\) 那么 \(i\) 就是答案。
时间复杂度 \(O(q \log n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
int B[50007];
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, q;
cin >> n >> q;
for (int i = 1;i <= n;i++) cin >> B[i], B[i] += B[i - 1];
while (q--) {
int t;
cin >> t;
cout << upper_bound(B + 1, B + n + 1, t) - B << '\n';
}
return 0;
}
最新文章
- Win10 UWP开发系列:使用VS2015 Update2+ionic开发第一个Cordova App
- 【ZJOI2007】棋盘制作 BZOJ1057
- “VS2013无法连接远程数据库”解决方案
- CSS3实现的超酷动态圆形悬浮效果
- CF Two Substrings
- mysql补集合计算
- 将 Shiro 作为应用的权限基础 四:shiro的配置说明
- mybatis的配置和使用
- Spring Boot thymeleaf模版支持,css,js等静态文件添加
- 构建基于Suricata+Splunk的IDS入侵检测系统
- Java容器深入浅出之PriorityQueue、ArrayDeque和LinkedList
- can not connect to MySQL server on ";10.30.48.153";(13)
- 第 0 课 Golang环境搭建
- XV6操作系统代码阅读心得(三):锁
- 【转载】Android中attr自定义标签详解
- 《DSP using MATLAB》示例Example 8.8
- MicroRNA 详解
- CentOS6.5更改语言设置
- Google File System设计方面的问题汇总
- CSS之元素