长沙网站制作哪家好,wordpress出境游,营销型网站知识,利津网站建设题解#xff1a; 来自学长们思路#xff1a; 其中一种正解是写单调队列。限制队列内的数单调递增#xff0c;方法为每当新来的数据比当前队尾数据小时队 尾出列#xff0c;直到能够插入当前值#xff0c;这保证了队头永远是最小值。因此总体思路是队尾不断插入新值的同时 … 题解 来自学长们思路 其中一种正解是写单调队列。限制队列内的数单调递增方法为每当新来的数据比当前队尾数据小时队 尾出列直到能够插入当前值这保证了队头永远是最小值。因此总体思路是队尾不断插入新值的同时 不断输出当前队头元素。在输出队头元素时有两点要注意 1. 队尾前进 m次后再开始输出。 2. 确认当前队头值的下标仍在区间范围内反之则需要队头出队直到进入当前区间。 #include iostream
#include vector
using namespace std;
int main()
{int n, m;cin n m;vectorintarr(n 1); //用于存放数据vectorintq(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--; //尾移动弹出元素过程中要保证更小的元素能作为队头所以才是(headtail)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发现160(因为arr[q[tail]]arr[q[0]]arr[0]0)然后16的下标1经由q[tail]存到了q[1]的位置也是head所指的位置。然后遇到5发现516,就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发现59,tail--tail变为了2然后56,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-21)5m发现第一个5~13是的长度是5而第一5并不在13所在的区间范围中这时head,往后移一位head变为2输出符合13所在区间的最小的数即下标为5的那个5。 同理然后就是q[4]7q[5]8,直到遇到8下标为9发现经过tail的移动以及覆盖q[2]5,q[3]9,但这时候9-q[head]1(9-51)5m,这时第二个5并不是8所在范围中这时head,head3;输出符合8所在区间的最小的数即8。 同理直到for遍历n次后 输出 5 5 5 5 5 8 8 总之队列q中存放的是每个长度为m的组中最小值的下标 当然,head1,tail0就是为了方便通过移动tail位置用tail弹出队尾元素以及弹出队头元素当第一个数据的下标输入进去后tail通过自增tail1head就拿16和后面的5来说16输入进去后tailhead1;但是516,这是tail--,变为0但是head仍然为1后续经过tail让tail重新变为1,5的下标覆盖16的下标。 然后是 head tail条件这是为了防止已经把队列有效元素都弹完了还继续弹。比如head3时如果没有该条件限制当遇到一个整个数据中最新的数比如1时会不断弹哪怕tail2了还在移动tail位置此时等到再插入该数下标时会把下标放在无效位置,因为head3,q[3]以后才是有效位置 参考(来自学长们题解
