AWTF2024A Moving Slimes 题解

发现史莱姆不合并也不会影响答案，所以就不用考虑合并了。

这样处理之后，史莱姆的移动可以看作是受到与其不在同一位置的史莱姆的吸引所完成的，每只史莱姆可以给其他史莱姆一个单位的吸引力。

因为每只史莱姆提供的吸引力是恒定的，所以考虑把吸引力放在它们的重心上，设 \(pre_i\) 表示坐标比第 \(i\) 只史莱姆小的所有史莱姆的重心的坐标，\(suf_i\) 表示坐标比第 \(i\) 只史莱姆大的所有史莱姆的重心的坐标。

设 \(d_i = suf_i - pre_i\)，如果对所有史莱姆 \(i\)，都有 \(d_i = 0\)，则说明所有史莱姆已经处在同一个坐标上，满足终止条件。

只需要考虑每个 \(d_i\) 需要多长时间减少到 \(0\)。为了方便，称从开始移动直到有两个史莱姆发生碰撞为一轮。

每一轮结束后，因为发生了碰撞，所以 \(d_i\) 至少减少 \(k\)，得到答案的下界 \(\frac {\max\{d_i\}} k\)。

显然史莱姆的相对顺序是不变的，终止条件也可以表述为对除最后一个以外的史莱姆 \(i\)，\(a_i = a_{i + 1}\)。为了得到答案的上界，考虑尽可能延长这个条件达成的时间，则答案的上界也是 \(\frac {\max\{d_i\}} k\)。

为了最大化 \(\max\{d_i\}\)，显然选择的 \(k\) 只史莱姆来自一段前缀和一段后缀。枚举每一对前后缀，容易在 \(O(1)\) 的时间内计算这一方案的答案，时间复杂度 \(O(n)\)。

#include <iomanip>
#include <iostream>

using namespace std;

typedef long long ll;
typedef long double ld;

int n, k;
int a[250005];
ll f[250005];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        f[i] = f[i - 1] + a[i];
    }
    ld ans = 0;
    for (int i = 1; i < k; ++i)
        ans = max(ans, (ld)(f[n] - f[n - k + i]) / (k - i) - (ld)f[i] / i);
    cout << fixed << setprecision(20) << ans / k << endl;
    return 0;
}