解题思路
歌曲由 $N$ 个音符组成,第 $i$ 个音符持续 $B_i$ 拍。在时间 $0$ 开始播放歌曲;
从时间 $0$ 到时间 $B_1$之前播放音符 $1$,从时间 $B_1$ 到时间 $B_1 + B_2$ 之前播放音符 2,依此类推。
询问 $Q$ 个如下述形式的问题:在从时间 $T$ 到时间 $T + 1$ 之前的间隔中,应该演奏哪个音符?
在时间 $T$ 在$[0, B_1-1]$范围内时,演奏音符 1;
在时间 TT 在 $[B_1, B_1 + B_2 - 1]$ 范围内时,演奏音符 2;
依此类推。
使用 map 记录时间节点 $B_1 - 1, B_1+B_2-1,\dots$ 对应的音符,
就可以使用 map::lower_bound()
函数得出对应的演奏音符。
则有答案
#include <iostream>
#include <map>
using namespace std;
int main(){
int n, t;
cin >> n >> t;
int ti = 0;
map <int, int> mp;
for(int i = 1;i <= n;i ++){
int t;
cin >> t;
ti += t;
mp[ti - 1] = i;
}
for(int i = 0;i < t;i ++){
int q;
cin >> q;
cout << mp.lower_bound(q)->second << '\n';
}
}
求关注