正经题解｜听歌识曲

模拟找歌曲的过程，用数组来存储信息。数组有两种表示形式，数组下标表示秒数，数组元素表示对应歌曲的编号，即 $a[i]=x$ 表示第 $i$ 秒是第 $x$ 首歌。这种存法的好处在于想找的时间能够直接找到对应歌曲编号，但需要大量的数组空间。题目中总时间可能会到达 $10^{10}$ 秒，所以这种存法只能通过部分测试点。
另一种存法是数组下标表示歌曲编号，数组元素表示当前歌曲的持续时间，即$a[i]=x$ 表示第 $i$ 首歌持续 $x$ 秒。
记录每首歌的持续时间，可以计算得到每首歌的结束时间。
当前歌曲结束时间=上一首歌的结束时间+当前歌曲持续时间。
因为只要找一首歌，所以用数组记录每首歌的结束时间，和前缀和的写法一样。找到第一个大于等于想找时间的结束时间，对应编号的歌名即为答案。
如果题目想要找多个时间对应的歌曲名，可以考虑二分的方法在前缀和数组中进行查找。

#include <bits/stdc++.h>
using namespace std;
long long a[100010];
long long b[100010];
string s[100010];
int main () {
	long long n,m;
	cin>>n>>m;
	b[0]=0;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>s[i];
		b[i]=b[i-1]+a[i];//记录每首歌的结束时间
	}
	long long ans=0;
	for(int i=1;i<=n;i++){
		if(m<=b[i]){//找到第一个大于等于所求时间的歌曲
			ans=i;
			break;
		}
	}
	cout<<s[ans];
	return 0;
}