CF773E Blog Post Rating

· · 题解

经过证明我们可以得到：
在最优策略下（对a_i进行升序排序），我们的评分呈如下趋势。

那我们设转折点为 s (1 \le s \le n )点，这个点必为负数，我们考虑反证法：
若该点为正点，则： a_s>a_{s+1} 显然不符合不降序排序后的结果，证明成功。

则 a_s=-s ，移项得： a_s+s=0 。
又推导可得 a_i+i 单调递增。所以我们可以用权值线段树动态维护（因为动态所以不能用二分）。
我们设 f_i 为第 i 个人评分之后得评分，得到递推式：

f(i) = \begin{cases} a_1=f_{i-1} & f_i=f_{i-1} \\ a_i>f_{i-1} & f_i=f_{i-1}+1 \end{cases}

我们又得到：

f_i=\min(f_{i-1}+1,a_i)

拆项，得：

f_i= \min(f_{i-2}+2,a_{i-1}+1,a_i)

一直拆到 i 变成 s 点为止。
这题解了，代码不贴，自己思考。