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

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇