毛豆

用户名：liuyt

访问量：16848

签　名：

等　　级
排　　名	1025
经　　验	3310
参赛次数	3
文章发表	34
年　　龄	22
在职情况	学生
学　　校	燕山大学
专　　业	计算机

　　自我简介：

TA的其他文章

肺炎大作战-题解(C++代码)
浏览：186

你可能喜欢

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

优先队列解决滑块问题

　　作者: 毛豆　　　　发表时间：2019-07-23 12:14:40 浏览：757　|　评论：0　

下面妖怪君给大家说一下优先队列的用法
先说一下队列的用法
首先引入头文件
	#include<queue>
queue<类型int> q;
back()返回最后一个元素
empty()如果队列空则返回真
front()返回第一个元素
pop()删除第一个元素
push()在末尾加入一个元素
size()返回队列中元素的个数
while (!Q.empty()) Q.pop();清空队列
队头队尾需要加_front()或者_back()
还有队列中最常用的结构体
	struct Node
	{
	int x,pos;
	Node(int xx,int pp)
	{
		x=xx;pos=pp;
	}
	};
优先队列就是自动排序的队列
无论怎么插入，他都会自动按顺序排好
定义方式如下
priority_queue <int,vector<int>,less<int> > p;
priority_queue <int,vector<int>,greater<int> > q;
自己测试好像只能用top而不能用front和back

比如滑块问题用队列就很容易解决
描述
给定一个长度为n（n<=10^6）的数组。有一个大小为k的滑动窗口从数组的最左端移动到最右端。你可以看到窗口中的k个数字。窗口每次向右滑动一个数字的距离。
下面是一个例子：
数组是 [1 3 -1 -3 5 3 6 7]， k = 3。

窗口位置	最小值	最大值
[1  3  -1] -3  5  3  6  7 	-1	3
 1 [3  -1  -3] 5  3  6  7 	-3	3
 1  3 [-1  -3  5] 3  6  7 	-3	5
 1  3  -1 [-3  5  3] 6  7 	-3	5
 1  3  -1  -3 [5  3  6] 7 	3	6
 1  3  -1  -3  5 [3  6  7]	3	7

你的任务是得到滑动窗口在每个位置时的最大值和最小值。

输入
输入包括两行。
第一行包括n和k，分别表示数组的长度和窗口的大小。
第二行包括n个数字。
输出
输出包括两行。
第一行包括窗口从左至右移动的每个位置的最小值。
第二行包括窗口从左至右移动的每个位置的最大值。
样例输入
8 3
1 3 -1 -3 5 3 6 7
样例输出
-1 -3 -3 -3 3 3
3 3 5 5 6 7
	#include<iostream>
	#include<cmath>
	#include<cstring>
	#include<algorithm>
	#include<iomanip>
	#include<queue>
	#include<stack>
	#include<vector>
	#include<set>
	#include<map>
	using namespace std;
	int n,k,a;
	struct Node
	{
	int x,pos;
	Node(int xx,int pp)
	{
		x=xx;pos=pp;
	}
	};
	deque<Node>p;
	deque<Node>q;
	int Max[1000005];
	int Min[1000005];
	int main()
	{
	cin>>n>>k;
	for(int i=0;i<n;++i)
	{
		cin>>a;
		while(!p.empty()&&p.back().x>=a)//控制大小
		{
			p.pop_back();
		}
		p.push_back(Node(a,i));
		if(p.back().pos-p.front().pos>=k)//控制滑块
		{
			p.pop_front();
		}
		while(!q.empty()&&q.back().x<=a)
		{
			q.pop_back();
		}
		q.push_back(Node(a,i));
		if(q.back().pos-q.front().pos>=k)
		{
			q.pop_front();
		}
		if(i>=k-1)
		Min[i-k+1]=p.front().x;
		Max[i-k+1]=q.front().x;
	}
	for(int i=0;i<=n-k;++i)
	{
		cout<<Min[i]<<" ";
	}
	cout<<endl;
	for(int i=0;i<=n-k;++i)
	{
		cout<<Max[i]<<" ";
	}
	cout<<endl;
	return 0;
	}
如果用数组要很复杂，但是队列就很简单，后期妖怪君还会研究堆的使用，不懂得地方可以留言，

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

毛豆

TA的其他文章

你可能喜欢

C语言训练-求车速（C语言代码）

简单的a+b （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

简单的a+b （C语言代码）

优先队列解决滑块问题

评论区

精彩推荐

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

C语言训练-素数问题（C语言代码）

不容易系列2 （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

剪刀石头布（C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

【偶数求和】（C语言代码）

Tom数（C语言代码）

Tom数（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

毛豆

TA的其他文章

你可能喜欢

C语言训练-求车速 （C语言代码）

简单的a+b （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

简单的a+b （C语言代码）

优先队列解决滑块问题

评论区

精彩推荐

C语言训练-求具有abcd=(ab+cd)2性质的四位数 （C语言代码）

C语言训练-素数问题 （C语言代码）

不容易系列2 （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

剪刀石头布 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

【偶数求和】 （C语言代码）

Tom数 （C语言代码）

Tom数 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-求车速（C语言代码）

　　评论区

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

C语言训练-素数问题（C语言代码）

剪刀石头布（C语言代码）

【偶数求和】（C语言代码）

Tom数（C语言代码）

Tom数（C语言代码）