AGC27B Garbage Collector 题解

401rk8 · 2022-05-01 20:27:24 · 题解

官方题解的做法，比现有题解更简洁的表述

一些观察：

• 捡垃圾的总代价 nX 为定值，最后加上
• 扔掉的垃圾 p_{1}>\cdots>p_{m}>p_{m+1}=0 确定时，最优策略是先走到 p_{1}，再一边往回走一边捡垃圾，路上花费的代价是 p_{1}+\sum_{i=1}^{m}(i+1)^{2}(p_{i}-p_{i+1})=5p_{1}+\sum_{i=2}^{m}(2i+1)p_{i}

考虑枚举扔垃圾的次数 k，那么扔垃圾的总代价 kX 也是定值。发现 p 前乘的系数不降，贪心地给较大的 p 安排较小的系数（x+y 一定时，|x-y| 越大，x^{2}+y^{2} 越小），因此一定是最大的 k 个 x 作为 p_1，次大的 k 个作为 p_2\cdots\cdots 枚举系数，使用前缀和即可 O(\frac{n}{k}) 计算一个 k 的答案，时间复杂度 O(n\ln n)

注意虽然答案只有 10^{14} 级别（k=n），但某些 k（比如 k=1）时答案会达到 10^{19} 级别，我偷懒直接用 __int128 了

code