企业官网建设流程全解析

域名需要跟网站名称一致么,讯响模板网站,学校网站建设内容,中企动力做网站贵吗单调队列 1. 什么是单调队列#xff1f; 单调队列#xff0c;顾名思义#xff0c;就是存储的元素要么单调递增要么单调递减的队列。注意#xff0c;这⾥的队列和普通 的队列不⼀样#xff0c;是⼀个双端队列。2. 单调队列解决的问题 ⼀般⽤于解决滑动窗⼝内最⼤值最⼩值…单调队列1.什么是单调队列单调队列顾名思义就是存储的元素要么单调递增要么单调递减的队列。注意这⾥的队列和普通 的队列不⼀样是⼀个双端队列。2.单调队列解决的问题⼀般⽤于解决滑动窗⼝内最⼤值最⼩值问题以及优化动态规划。2.1【模板】单调队列题⽬来源 洛⾕题⽬链接P1886 滑动窗⼝ /【模板】单调队列难度系数 ★★题目描述有一个长为 n 的序列 a以及一个大小为 k 的窗口。现在这个窗口从左边开始向右滑动每次滑动一个单位求出每次滑动后窗口中的最小值和最大值。例如对于序列 [1,3,−1,−3,5,3,6,7] 以及 k3有如下过程窗口位置[1 3 -1] -3 5 3 6 7 1 [3 -1 -3] 5 3 6 7 1 3 [-1 -3 5] 3 6 7 1 3 -1 [-3 5 3] 6 7 1 3 -1 -3 [5 3 6] 7 1 3 -1 -3 5 [3 6 7]​最小值−1−3−3−333​最大值335567​​输入格式输入一共有两行第一行有两个正整数 n,k第二行有 n 个整数表示序列 a。输出格式输出共两行第一行为每次窗口滑动的最小值第二行为每次窗口滑动的最大值。输入输出样例输入 #1复制8 3 1 3 -1 -3 5 3 6 7输出 #1复制-1 -3 -3 -3 3 3 3 3 5 5 6 7说明/提示【数据范围】对于 50% 的数据1≤n≤105对于 100% 的数据1≤k≤n≤106ai​∈[−231,231)。【解法】窗⼝内最⼤值从左往右遍历元素维护⼀个单调递减的队列•当前元素进队之后注意维护队列内的元素在⼤⼩为 k 的窗⼝内•此时队头元素就是最⼤值。窗⼝内最⼩值从左往右遍历元素维护⼀个单调递增的队列•当前元素进队之后注意维护队列内的元素在⼤⼩为 k 的窗⼝内•此时队头元素就是最⼩值。【参考代码】#include iostream #include deque // 行2导入双端队列可以从队头/队尾删元素 using namespace std; const int N 1e6 10; // 行4序列最长100万10个数字 int n, k; // 行5n是序列长度k是窗口大小 int a[N]; // 行6存储序列的数字a[1]是第一个a[2]第二个... int main() // 行7程序入口 { cin n k; // 行9读入n和k比如8和3 for(int i 1; i n; i) cin a[i]; // 行10读入序列存到a[1]-a[8] dequeint q; // 行12双端队列存的是数字的“下标”不是数字本身 // 第一部分算窗口最小值维护单调递增队列 for(int i 1; i n; i) // 行15遍历每个数字从第1个到第8个 { // 行17如果队列不为空且队尾下标对应的数字 当前数字 → 删掉队尾 while(q.size() a[q.back()] a[i]) q.pop_back(); q.push_back(i); // 行18把当前数字的下标加入队尾 // 行20判断队列里的数字是否超出窗口范围窗口长度不能超过k if(q.back() - q.front() 1 k) q.pop_front(); // 行22只有当i k时窗口已经滑够3个数字才输出队头的最小值 if(i k) cout a[q.front()] ; } cout endl; // 行24最小值输出完换行 // 第二部分算窗口最大值维护单调递减队列 q.clear(); // 行27清空队列重新用 for(int i 1; i n; i) // 行28再次遍历每个数字 { // 行30如果队列不为空且队尾下标对应的数字 当前数字 → 删掉队尾 while(q.size() a[q.back()] a[i]) q.pop_back(); q.push_back(i); // 行31把当前数字的下标加入队尾 // 行33判断是否超出窗口范围超出则删队头 if(q.back() - q.front() 1 k) q.pop_front(); // 行35i k时输出队头的最大值 if(i k) cout a[q.front()] ; } cout endl; // 行37最大值输出完换行 return 0; // 行38程序结束 }2.2质量检测题⽬来源 洛⾕题⽬链接P2251 质量检测难度系数★★题目描述为了检测生产流水线上总共 N 件产品的质量我们首先给每一件产品打一个分数 A 表示其品质然后统计前 M 件产品中质量最差的产品的分值 Qm​min{A1​,A2​,⋯,Am​}以及第 2 至第 M1 件的 Qm1​Qm2​…… 最后统计第 N−M1 至第 N 件的 Qn​。根据 Q 再做进一步评估。请你尽快求出 Q 序列。输入格式输入共两行。第一行共两个数 N、M由空格隔开。含义如前述。第二行共 N 个数表示 N 件产品的质量。输出格式输出共 N−M1 行。第 1 至 N−M1 行每行一个数第 i 行的数 QiM−1​。含义如前述。输入输出样例输入 #1复制10 4 16 5 6 9 5 13 14 20 8 12输出 #1复制5 5 5 5 5 8 8说明/提示[数据范围]对于 30% 的数据N≤1000。对于 100% 的数据M≤N≤105,Ai​≤106。【解法】滑动窗⼝内的最⼩值~#include iostream #include deque using namespace std; const int N 1e6 10; // 最多支持100万10个产品 int n, k; // n是产品总数k是窗口大小对应题目里的M int a[N]; // 存储每个产品的质量分a[1]是第1个a[2]是第2个... int main() { cin n k; // 读入n10k4 dequeint q; // 双端队列存的是“产品的下标”不是分数本身 // 遍历每个产品从第1个到第10个 for(int i 1; i n; i) { cin a[i]; // 读入当前产品的分数比如i1时读16i2时读5... // 核心1维护队列“从小到大”单调递增保证队头是最小值 // 如果队列不为空且队尾下标对应的分数 ≥ 当前分数 → 删掉队尾 while(q.size() a[q.back()] a[i]) q.pop_back(); q.push_back(i); // 把当前产品的下标加入队尾 // 核心2保证队列里的下标都在窗口内窗口长度不能超过k // 当前下标 - 队头下标 1 k → 队头超出窗口删掉 if(i - q.front() 1 k) q.pop_front(); // 核心3窗口滑够k个产品后输出队头对应的最小值每行一个 if(i k) cout a[q.front()] endl; } return 0; }