当前位置：首页 > news >正文

E-魔法猫咪（遇到过的题，做个笔记）

news 2025/9/2 19:17:58

题解：

来自学长们思路：

其中一种正解是写单调队列。限制队列内的数单调递增，方法为每当新来的数据比当前队尾数据小时队尾出列，直到能够插入当前值，这保证了队头永远是最小值。因此总体思路是队尾不断插入新值的同时不断输出当前队头元素。在输出队头元素时有两点要注意：

1. 队尾前进 m次后再开始输出。

2. 确认当前队头值的下标仍在区间范围内，反之则需要队头出队直到进入当前区间。

#include <iostream>
#include <vector>
using namespace std;
int main()
{int n, m;cin >> n >> m;vector<int>arr(n + 1);			//用于存放数据vector<int>q(n + 1);		//存最小数的下标int head = 1, tail = 0;			//模拟双向队列，把头定为 q[1]，尾先定为q[0]，且该队列是单调递增的for (int i = 1; i <= n; i++){cin >> arr[i];while (1)	//通过移动末尾的位置来弹出队尾元素，直到队尾能插入新的更小的数据{if (arr[i] < arr[q[tail]] && head <= tail)	tail--;	//尾移动弹出元素过程中，要保证更小的元素能作为队头所以才是(&&head<=tail)else{q[++tail] = i;		//将元素插入队尾break;		//更小数据插入后就结束循环}}if (i - q[head] + 1 > m)	head++;		//发现该元素与队头元素的距离超过了m，就让队头的位置往后移动，因为原先队头元素已经不是该元素所在区间范围中了if (i >= m)	cout << arr[q[head]] << endl;  //当判断过m个元素后才开始输出队头元素}return 0;}
就以样例为例，说下过程：

一开始第一个数是16，发现16>0(因为arr[q[tail]]=arr[q[0]]=arr[0]=0)，然后16的下标1经由q[++tail]存到了q[1]的位置，也是head所指的位置。然后遇到5，发现5<16,就tail--(tail从1变成了0），然后下一次循环，就由q[++tail]，tail变成1, 5的下标2覆盖了16的下标1。

然后6,9都＞5，分别让下标存到了q[2]=3,q[3]=4;在遇到9的时候，从16到9刚好满足m的长度，输出arr[q[head]]，而head这里存放的正是由16~9这4个数中最小的数--5的下标2。

然后遇到了5，发现5<9,tail--，tail变为了2，然后5<6,tail--，tail变为了1；然后下一次循环到else语句中，经由q[++tail]，tail变为2, 5的下标存到了q[2]=5。而5~5这4个数中最小的元素仍是第一个5（下标为2的那个5）,把这个5输出。

然后是13，这时，13的下标存到了q[3]=6,但是13的下标6-q[head]+1(6-2+1)=5>m，发现第一个5~13是的长度是5，而第一5并不在13所在的区间范围中，这时head++,往后移一位，head变为2，输出符合13所在区间的最小的数，即下标为5的那个5。

同理然后就是q[4]=7，q[5]=8,直到遇到8（下标为9），发现经过tail的移动以及覆盖，q[2]=5,q[3]=9,但这时候9-q[head]+1(9-5+1)=5>m,这时第二个5并不是8所在范围中，这时head++,head=3;输出符合8所在区间的最小的数，即8。

同理直到for遍历n次后

输出：

5 5 5 5 5 8 8

总之，队列q中存放的是，每个长度为m的组中最小值的下标

当然,head=1,tail=0，就是为了方便通过移动tail位置（用++tail）弹出队尾元素以及弹出队头元素（当第一个数据的下标输入进去后，tail通过自增，tail=1=head），就拿16和后面的5来说，16输入进去后，tail=head=1;但是5<16,这是tail--,变为0但是head仍然为1，后续经过++tail，让tail重新变为1,5的下标覆盖16的下标。

然后是&& head <= tail条件，这是为了防止已经把队列有效元素都弹完了，还继续弹。比如head=3时，如果没有该条件限制，当遇到一个整个数据中最新的数，比如1时，会不断弹，哪怕tail=2了，还在移动tail位置，此时等到再插入该数下标时，会把下标放在无效位置,因为head=3,q[3]以后才是有效位置