题解：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)

，代码巨短。

CPP

#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;
}

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

文章操作

题目传送门

相关推荐

评论

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