F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:祝各位Oier新年快乐,Rp++!
大视野在线测评-欢迎您
[ New Thread ]
Problem 4709 >> 斜率优化做法的精度问题
Izumihanako @ 2018-01-14 22:24:26
[ Quote ] [ Edit ] [ Delete ] 1#
rt,使用斜率优化做此题时
推导出y=kx+b的式子,其中kx那一坨是2*sum[i]*sum[j]*size[j]
x只能设为sum[j],而不能设为sum[j]*size[j](就是要把size[j]丢到斜率k里面),不然在判断斜率时会炸long long

对于x是sum[j]*size[j]的解决办法:
为了避免乘炸,判斜率需要就用除法,并且只能用大于号(或者在左侧加 -eps )
像这样:K(now,topp) > K(topp , topp-1)
Izumihanako @ 2018-01-14 22:25:16
[ Quote ] [ Edit ] [ Delete ] 2#
是大于等于就会WA
这个精度问题卡了me一晚上= =
心塞塞
[Top] [Previous Page] [Next Page]

HOME Back