CF1344D 题解

题意

传送门

给定一个长度为 \(n\) 的数组 \(a_i\)，构造自然数数组 \(b_i\) 满足：

• \(\forall i,b_i \in [0,a_i]\)
• \(\sum_{i=1}^n b_i=k\)

并最大化 \(\sum_{i=1}^n b_i(a_i-b_i^2)\)。

\(1 \le n \le 10^5,1 \le a_i \le 10^9\)。

题解

一道挺新颖的数学题，来记一下。

设 \(f(x,i)\) 表示 \(x(a_i-x^2)\)。这是一个三次函数，比较难看。

使用一个常见的套路，设 \(g(x,i)=f(x,i)-f(x-1,i)\)。这样就变成了二次函数。

再对其求导，得到 \(g'(x,i)=-6x+3\)。因为 \(x \in N^*\)，故 \(g\) 是单调递减的。

结合 \(g\) 的实际意义，不难得出一个 \(O(k \log n)\) 的算法：动态加 \(b\)，用大根堆维护所有 \(g(b_i+1,i)\)，每次取堆顶 \(i\)，将 \(b_i\) 自增。

更进一步，利用 \(g\) 的单调性，二分一个 \(t\)，对所有 \(i\) 求出满足 \(g(x,i) \ge t\) 的最大 \(x\)。判断 \(\sum x\) 与 \(k\) 的大小关系即可。复杂度 \(O(n \log^2 V)\)。

其实也可以不用二分，因为 \(g(x,i)\) 是只和 \(x\) 有关的二次函数，直接算就行了。复杂度 \(O(n \log V)\)。