题解：AT_arc128_c [ARC128C] Max Dot

Imaginative · 2025-10-15 23:24:42 · 题解

因为从前往后推时前面可能为 0 而后往前推则无需判断，因此从后往前推。最终的序列求得一定是阶梯状的，刚开始有最直接的两种贪心想法（令 val 为填到这个位置还剩多少值）：

1. 从后往前找到最大值，并让这个位置（设为 i）到最大值（位置为 pos）的值赋上 \frac{val}{i-pos+1}
2. 从后往前记录后缀值，每一次提供的答案为 \frac{val}{i-pos+1} \times \sum_{j=pos}^{i} a_j

• 第一种显然错误，如果前面的特别大而后面的特别小。比如 7~8~9~1 且 m=4,s=4 就会赋为 0~0~2~2 而正确答案应赋为 1~1~1~1。
• 第二种看似正确，这种贪心保证了每一次选数的最优值。因为每一次都考虑了整个序列，且后面的选数不影响前几次选的因此局部最优解为全局最优解。

但是显然我们还没考虑最大值上限的问题。我一开始是想如果 \frac{val}{i-pos+1} 超过 m 再调整回去。但是如果每一次 \frac{val}{i-pos+1} 都小于 m 那么我们就会给后面的数浪费了很多权值（数又大又后时）。

注意到我们之前的算法是线性的。为什么不是 n^2 的，因为如果每一次 pos 减的少那么 val 减的必然大，反之亦然。每次填完或者 val=0 了就退出必能保证线性。

又注意到 m 最多出现 n 次，因此我们每次暴力枚举