10181. 「一本通 5.5 练习 2」绿色通道

题意

高二数学《绿色通道》总共有 $n$ 道题目要抄,编号 $1\dots n$,抄第 $i$ 题要花 $a_i$ 分钟。小 Y 决定只用不超过 $t$ 分钟抄这个,因此必然有空着的题。每道题要么不写,要么抄完,不能写一半。下标连续的一些空题称为一个空题段,它的长度就是所包含的题目数。这样应付自然会引起马老师的愤怒,最长的空题段越长,马老师越生气。
现在,小 Y 想知道他在这 $t$ 分钟内写哪些题,才能够尽量减轻马老师的怒火。由于小 Y 很聪明,你只要告诉他最长的空题段至少有多长就可以了,不需输出方案。

思路

很明显这道题可以使用二分来寻找最短的最长空题段。(有点绕口)

90分做法

思路

然而发现这道题的数据:
对于所有数据,$0<n \le 5\times 10^4,0<a_i\le 3000,0<t\le 10^8$
所以直接二分+check(dp)肯定是不行的。
这样复杂度达到了$O(logN \times N^2)$
但是这样能拿90分(逃:
在使用dp check时:
设$f[i]$表示前i道题目的最少时间。
那么:$f[i]=min(f[i],f[j]+a[i])$且$max(0,i-t-1)\leq j \leq i-1$

Code

100分做法

思路

与90分做法差不多,只是把check的dp进行单调队列优化:

Code

暂无评论

发送评论


				
上一篇
下一篇