题解：P12225 [蓝桥杯 2023 国 Java B] 游戏

· · 题解

题目传送门

记 f(l,r) 表示区间 [l,r] 的最大值，g(l,r) 表示区间 [l,r] 的最小值，因为每种方案选中的概率均为 \frac{1}{(n-k+1)^2}，可以得到答案为

\frac{\sum_{i=1}^{i+k-1\leq n}\sum_{j=1}^{j+k-1\leq n}f(i,i+k-1)-g(j,j+k-1)}{(n-k+1)^2}

考虑每个 f(l,r) 和 g(l,r) 对答案的贡献，显然 f(l,r) 被当了 n-k+1 次被减数，g(l,r) 被当了 n-k+1 次减数，可将答案化简为

\frac{\sum_{i=1}^{i+k-1\leq n}f(i,i+k-1)-g(i,i+k-1)}{n-k+1}

那么只需要快速求出 f 和 g 即可，使用单调队列或 st 表或线段树均可。这里我懒狗用 std::multiset 代替了单调队列做滑动窗口，时间复杂度 O(n\log n)，代码巨短。

#include <bits/stdc++.h>
using namespace std;
#define il inline
typedef long long ll;
const int N = 1e5 + 10;
int a[N], n, k;
multiset<int> s;
int main()
{
    cin >> n >> k;
    for(int i = 1;i <= n;++i) cin >> a[i];
    ll s1 = 0, s2 = 0;
    for(int i = 1;i < k;++i) s.insert(a[i]);
    for(int i = k;i <= n;++i)
    {
        s.insert(a[i]);
        s1 += (*s.begin());
        s2 += (*s.rbegin());
        s.erase(s.find(a[i - k + 1]));
    }
    double ans = (s2 - s1) * 1.0 / (n - k + 1);
    printf("%.2lf", ans);
    return 0;
}