游戏-单调队列

问题描述

熊大和熊二在玩游戏。他们将 n 个正整数 a1,a2,...,an​ 排成一行，然后各用一个长度为 k 的框在这个数组中各自随机框选出一段长度为 k 的连续子序列（随机框选指在合法的 n−k+1 个连续子序列中均匀随机）。熊大记录了他框出的 k 个数中的最大值 P，熊二记录了他框出的 k 个数的最小值 Q，他们突然有个疑问：P−Q 的期望是多少？

输入描述

输入共 2 行。

第一行为两个正整数 n,k。

第二行为 n 个由空格隔开的正整数 a1​,a2​,...,an​。

输出描述

输出共 1 行，一个浮点数（请保留两位小数）。

样例输入

3 2
1 2 3

样例输出

1.00

样例说明

一共有四种情况：

熊大框出 [1,2]，P=2；熊二框出 [1,2]，Q=1，P−Q=1。

熊大框出 [1,2]，P=2；熊二框出 [2,3]，Q=2，P−Q=0。

熊大框出 [2,3]，P=3；熊二框出 [1,2]，Q=1，P−Q=2。

熊大框出 [2,3]，P=3；熊二框出 [2,3]，Q=2，P−Q=1。

所以 P−Q 的期望为(1+0+2+1)/4=1.00。

评测用例规模

对于 20% 的数据，保证 n≤102。

对于 40%40% 的数据，保证 n≤103。

对于 100% 的数据，保证 n≤105，0<ai≤109，0<k≤n。

运行限制

 解析：

要找出长度为k的框中的最大最小数字，相当于采用滑动窗口，从第一个开始一个一个的移动窗口，维护两个队列，看当前窗口中的数的最大最小。从题目中可以看出求最大-最小的平均值，相当于求最大值的和-最小值的和除以2.

找最大数：

 维护一个滑动窗口大小为k，一个递减队列存储序号。

首先处理队列中的序号是否在当前滑动窗口中，查看队首序号如果在窗口中不处理，否则弹出队列，继续查看。

然后处理新插入的数字，如果当前插入的数比队尾的数大，将队尾弹出，继续判断，因为要维护一个递减队列，队首最大，队尾最小。

将每一个滑动窗口队首元素求和

找最小数：

 维护一个滑动窗口大小为k，一个递增队列存储序号。

首先处理队列中的序号是否在当前滑动窗口中，查看队首序号如果在窗口中不处理，否则弹出队列，继续查看。

然后处理新插入的数字，如果当前插入的数比队尾的数小，将队尾弹出，继续判断，因为要维护一个递增队列，队首最小，队尾最大。

将每一个滑动窗口队首元素求和

求值：

n个数字可以正好划分n-k+1框

（最大和-最小和）/(n-k+1)

#include<iostream>
#include<string>
#include<cstring>
#include<deque>
using namespace std;
typedef long long ll;
const ll MAX = 1e5 + 4;
ll a[MAX];
deque<int> dqmax, dqmin;//存储序号
ll dmax = 0, dmin = 0;
int main()
{
	ll n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++)
	{
		//先看滑动窗口   离开滑动窗口的弹出队列
		while (!dqmax.empty() && dqmax.front() < i - k + 1)
		{
			dqmax.pop_front();
		}
		//递减队列  将小于a[i]弹出
		while (!dqmax.empty() && a[dqmax.back()] < a[i])
		{
			dqmax.pop_back();
		}
		dqmax.push_back(i);



		//先看滑动窗口   离开滑动窗口的弹出队列
		while (!dqmin.empty() && dqmin.front() < i - k + 1)
		{
			dqmin.pop_front();
		}
		//递增队列  将大于a[i]弹出
		while (!dqmin.empty() && a[dqmin.back()] > a[i])
		{
			dqmin.pop_back();
		}
		dqmin.push_back(i);


		//维护一个完整的滑动窗口i表示结束位  例如k=2时  i==2时才正好第一个滑动窗口
		if (i >= k)
		{
			dmax += a[dqmax.front()];
			dmin += a[dqmin.front()];
		}
	}
	printf("%.2f",1.0 * (dmax - dmin) / (n - k + 1));
	return 0;
}