高度由习惯堆积

分类 数学:凸包 下的文章

BZOJ2726 SDOI2012 任务安排

题目机器上有N个需要处理的任务,它们构成了一个序列。这些任务被标号为1到N,因此序列的排列为1,2,3...N。这N个任务被分成若干批,每批包含相邻的若干任务。从时刻0开始,这些任务被分批加工,第i个任务单独完成所需的时间是Ti。在每批任务开始前,机器需要启动时间S,而完成这批任务所需的时间是各个任务需要时间的总和。注意,同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系...

CF1143F U2

题目题目链接大意是:给你若干个点的坐标,点对之间画一条形如$f(x)=x^2+bx+c$的抛物线,问抛物线内最多的点有多少个。思路一道思维好题。首先抛物线上自然没有什么性质可供挖掘,所以考虑转化为直线。注意到$x^2$的系数是$1$,所以原式可化为$y-x^2=bx+c$这样的直线形式,于是点对之间就以直线的形式组合(坐标变为$(y-x^2,x)$)。于是原来的条件就转化为了不在直线上方的点...