$endless$endless 题解

题目

解题方法

这道题考点是贪心、二分查找和排序。
首先我们设$f_i$fi​表示用$i$i个魔法的最大路程，则我们贪心，每次选最大的那$i$i个魔法最优，因此
$f_i=l+\sum_{j=1}^{i}{a_j}$fi​=l+∑j=1i​aj​
注意，我们要把$a$a数组先排序再求解。
继续简化上式，可得递推式
$f_i=\begin{cases} f_{i-1}+a_i&1\leq i\leq n\\ l&i=0 \end{cases}$fi​={fi−1​+ai​l​1≤i≤ni=0​
那么我们可以用$O(n)$O(n)求出$f$f数组。

• $85$85分的方法：每一次只要循环找到一个比$t$t大的数，输出它并停止循环，就行了。时间复杂度为$O(nq)$O(nq)。
• 满分的方法：我们发现$f$f数组有单调性，所以只要二分答案就行了。时间复杂度为$O(q\log_2^n)$O(qlog2n​)。

注意，我们不用除法，直接乘过去就行了。
因为$s$s（路程）除以$t$t（时间）等于$v$v（速度）。
也就是$v=\frac{s}{t}$v=ts​，可得$s=vt$s=vt。
而现在我们要求$\frac{s}{t}>v$ts​>v，也就是$s>vt$s>vt。
这样就不用算除法了。
注意，一定要开$long\:long$longlong！！！