Problem4436--听歌识曲

4436: 听歌识曲

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

洛洛有一份私人歌单,歌单里面塞满了他喜欢的歌曲,像夏恋、雨道、彩月、幻昼……整整有好几百首。洛洛每天都要把他的歌单听一遍,以致于他都能知道在什么时候放的是什么歌。
洛洛在向你推荐了他的歌单之后,决定考考你,从他的歌单开始播放起,第 $t$ 秒正在播放的是第几首歌。

Input

第一行输入两个整数 $n$ 和 $t$,分别表示歌单的歌曲总数以及第 $t$ 秒播放哪首歌。
第二行有 $n$ 个整数,$A_1,\ A_2,\ ...,\ A_n$,分别表示歌单的第 $i$ 首歌将会播放多长时间。

Output

输出一个整数,表示歌单按顺序播放后,第 $t$ 秒播放的是第几首歌。

Constraints

对于 $30\%$ 的数据,保证 $1 ≤ n ≤ 3$;
对于 $60\%$ 的数据,保证 $1 ≤ n ≤ 2,000,\ 1 ≤ A_i ≤ 500$;
对于 $100\%$ 的数据,保证 $1 ≤ n ≤ 100,000,\ 1 ≤ A_i ≤ 1,000,\ 1 ≤ t ≤ \sum_{i=1}^{i\leq n} (A_i)$。

Sample 1 Input

3 5
5 5 5

Sample 1 Output

1
歌单中总共有三首歌: 第一首歌播放 $5$ 秒,占第 $1 \sim 5$ 秒; 第二首歌播放 $5$ 秒,占第 $6 \sim 10$ 秒; 第三首歌播放 $5$ 秒,占第 $11 \sim 15$ 秒。 所以第 $5$ 秒播放的是第一首歌曲。

Sample 2 Input

3 5
1 3 5

Sample 2 Output

3
歌单中总共有三首歌: 第一首歌播放 $1$ 秒,占第 $1$ 秒; 第二首歌播放 $3$ 秒,占第 $2$~$4$ 秒; 第三首歌播放 $5$ 秒,占第 $5$~$9$ 秒。 所以第 $5$ 秒播放的是第三首歌曲。

HINT

问题来源:2019年绍兴市第十七届少儿信息学竞赛复赛

REF Vedio

Source/Category

基础算法 4.3.差分