[LOJ10181]绿色通道


传送门

一看到求什么“最大的最小值”,“最小的最大值”就马上想到二分(还有可能是单调队列)
再仔细看看题目,貌似没什么头绪,但答案似乎存在单调性,果断二分。
答案肯定在0到n范围内。
设\(f[i]\)为做到第\(i\)个作业时所需要花的最短时间。
假如我们可以空\(k\)道题(二分出来的)
\(f[i]=min(f[i],f[j]+a[i])\)
其中 $i-k+1 \le j < i

如果你想要满分,就要减少枚举量,就是减少枚举j的次数。
我们要维护一个区间最小数,可以用线段树来写,我这里采用的是优先队列。
采用优先队列有一个原则,那就是队列里的元素要单调,并且还要有另一个条件限制它们,我比较喜欢叫做“保质期”(因为保质期是不变的但是时间在变)
这个题目单调队列里的元素的保质期就是下标,如果他的下表不满足上面的枚举j的条件,这个元素就“过期”了

2 thoughts to “[LOJ10181]绿色通道”

发表评论

电子邮件地址不会被公开。 必填项已用*标注