A TubeTube Feedtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputMushroom Filippov cooked himself a meal and while having his lunch he decided to wat

题意

• 有 $n$ 个视频，第 $i$ 个视频的长度为 $a_i$ 秒，趣味值为 $b_i$。
• 现在你需要找到一个视频，使得你能在 $t$ 秒内观看完这个视频，且这个视频的趣味值最大，输出这个视频的编号。

思路

我们可以先考虑暴力的做法，枚举每个视频，再判断这个视频是否能在规定时间内看完。

时间复杂度为 $\mathcal{O}(n^2)$，不过这个复杂度是可以通过的。

考虑到我们要找到的是趣味值最大的视频，我们可以先按照趣味值从大到小排序。然后对于每个视频，我们看看能否在规定时间内看完，能的话就直接输出。

时间复杂度为 $\mathcal{O}(n\log n)$。

代码