codeforces 535 C.Tavas and karafs (解方程)

http://codeforces.com/problemset/problem/535/C
题读了好几遍才读懂。
题意是给出一个等差数列,操作严格要求从最左边不为零的连续m个数减去1,最多执行t次后问离最左边最远的位置在哪里。
有两个限制条件…一个是本身的si不能大于t,否则无法吃完。
还有一个是从sl到sr的和不能超过m*t (比赛的时候考虑的不周到。。实际上只有当r-l+1比m大的时候才是m,也就是说要取min(m,l-r+1))
这题正解应该是二分….直接Lower_bound。。。看到也有人用前缀和搞的。
我是解方程了(貌似是个傻逼做法)….
可以列出一个关于r的一元二次方程。。。然后求根公式2333
方程是:

 

然后再和第一个条件得到的r比较取小的就是结果…..

等周末把这题的二分解法也写一些。

下面是蒟蒻傻逼的数学方恒解法的代码:

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz