题解：AT_abc389_e [ABC389E] Square Price

Laisira · 2025-01-20 10:42:16 · 题解

化一下式子就是 j^2 = \sum_{i=1}^{j}(2\times i-1)。

每选择一个额外数的代价被拆开了，显然贪心的选择代价最小的，暴力模拟是会 TLE。

不难发现大多取数代价都是小于等于一个数 W 的，注意是大多。

然后就可以二分一个值 W，然后再贪一遍把零碎的贡献加上，时间复杂度 O(n\log M +n\log n)。

再说一下大多代价都是小于等于一个数 W 的，由于每个数的贡献小于等于 1，所以选择最小数一定不劣。