涉及 队列 单调队列 滑动窗口 单调队列队尾进队出队 队头 出队 前提单调 (快速获取最大值最小值) 滑动窗口维护一段连续区间 定长 区间长固定 不定长 区间长度动态变化P1886 【模板】单调队列 / 滑动窗口涉及单调队列滑动窗口定区间解题过程其实这个模板题是第二次看了 但是还是刚看到题目 之后 还是蛮模糊的平时看到数组内求什么最大值 最小值都是暴力直接循环for(intl1;lk-1n;l){intminvINT_MAX;for(intil;ilk-1;i)minvmin(minv,a[i]);coutminv ;}像这样直接去遍历无疑 肯定是会超限的 那么就应该需要去优化了 也就是 滑动窗口 去维护一段区间 再借助单调队列 去维护区间内的最值for(ll i1;in;i){while(hta[q[t]]a[i]){t--;}q[t]i;while(q[h]i-k1){h;}if(ik){couta[q[h]] ;}}在维护区间最小值时 维护队列内下标对应的数值 单调递增核心1.去队尾维护单调性在向队列内加入新元素时如果队尾元素对应的数值 新加入的下标对应的数值 说明队尾旧元素不可能成为后续窗口最小值直接弹出队尾直到队尾数值新加入的数值即新加入的数值永远不可能成为最小值再把i入队2.队头剔除越界元素若队头下标不在当前窗口范围 i-k1队头下标i就从队头弹出此时队头就是当前窗口最小值的下标。代码实现#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second using namespace std; int main() { IOS ll k,n; ll h,t; cinnk; vectorlla(n5); vectorllq(n5); for(int i1;in;i) { cina[i]; } h1;t0; for(ll i1;in;i) { while(hta[q[t]]a[i]) { t--; } q[t]i; while(q[h]i-k1) { h; } if(ik) { couta[q[h]] ; } } coutendl; h1;t0; for(ll i1;in;i) { while(hta[q[t]]a[i]) { t--; } q[t]i; while(q[h]i-k1) { h; } if(ik) { couta[q[h]] ; } } // coutfixedsetprecision(x) ; return 0; }[P2058 NOIP 2016 普及组] 海港 - 洛谷# P2058 [NOIP 2016 普及组] 海港涉及点 滑动窗口普通队列解题过程已经知道t是严格升序 题目给出船只到达时间 t 单调递增采用滑动窗口 普通队列实现队列queue先进先出 将t 与 国籍x捆绑到一起(利用结构体)q.push({t,x});先用 cnt 记录当前窗口内国籍 x 的乘客数量kind 存窗口内不同国籍总数若入队前 cnt[x]0说明是新增国籍kind 执行 cnt[x]然后入队完成后 通过一个while循环去清理过期乘客 ti - 86400 tp ti利用滑动窗口去查 while(!q.empty()q.front().tt-N)若队首乘客满足 q.front().t ≤ t - 86400 表示超出 24 小时窗口 取出队首国籍 xx cnt[xx]–若 cnt[xx]0窗口内不存在该国籍kind-- 弹出队首代码实现//P2058 #includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second using namespace std; const int N86400; const int M1e55; struct ship{ ll t; ll x; }; ll cnt[M]; int main() { IOS ll n; cinn; queueshipq; ll kind0; for(ll i1;in;i) { ll t,x; ll k; cintk; for(ll j1;jk;j) { cinx; q.push({t,x}); if(!cnt[x]) { kind; } cnt[x]; } while(!q.empty()q.front().tt-N) { ll xxq.front().x; cnt[xx]--; if(!cnt[xx])kind--; q.pop(); } coutkindendl; } // coutfixedsetprecision(x) ; return 0; }P1714 切蛋糕 - 洛谷P1714 切蛋糕涉及 前缀和 单调队列 滑动窗口最值不定长区间解题过程由题目可以看出是 找最大区间和6 31 -2 3 -4 5 -6 a[i]1 -1 2 -2 3 -3 sum[i]起点i为4时(1km)1 -2 3 (-4) 5 -6 a[i]k1 结果为sum[i]-sum[i-1]-41 -2 (3 -4) 5 -6 a[i]k2 结果为sum[i]-sum[i-2]-11 (-2 3 -4) 5 -6 a[i]k3 结果为sum[i]-sum[i-3]-3…km 结果为sum[i]-sum[i-m]sum[R]-sum[L-1] 区间长度为 1R-L1msum[i]-sum[l] 假定lL-1 1i-lm即区间范围 i-mli-1ansmax(sum[i]-sum[l]) (i-mli-1)等价于anssum[i]-min(sum[l]) 暴力 解题范围太大超限写过上面两道题之后 可以说 找最值 肯定还是单调队列滑动窗口最快了找最大值 -单调队列滑动窗口-用一个queue去存下标代码实现//P1714 #includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second using namespace std; ll ans-233333333; int main() { IOS ll n,m; cinnm; vectorllp(n3); vectorllsum(n10); dequellq; for(ll i1;in;i) { cinp[i]; sum[i]sum[i-1]p[i]; } q.push_back(0);// 初始放入下标0sum[0]0作为起点 for(ll i1;in;i) {//移除队头 下标超出i-m范围长度超过m while(q.front()mi) // while (!(li-m)) { q.pop_front(); } //sum[i] - 最小sum[q.front()] ansmax(ans,sum[i]-sum[q.front()]); //维护单调递增队列队尾前缀和 当前sum[i]就弹出 找最小值 while(!q.empty()sum[q.back()]sum[i]) { q.pop_back(); } q.push_back(i); } coutansendl; // coutfixedsetprecision(x) ; return 0; }
第一周 题目练习（queue）洛谷P1886 P1714 P2058
涉及 队列 单调队列 滑动窗口 单调队列队尾进队出队 队头 出队 前提单调 (快速获取最大值最小值) 滑动窗口维护一段连续区间 定长 区间长固定 不定长 区间长度动态变化P1886 【模板】单调队列 / 滑动窗口涉及单调队列滑动窗口定区间解题过程其实这个模板题是第二次看了 但是还是刚看到题目 之后 还是蛮模糊的平时看到数组内求什么最大值 最小值都是暴力直接循环for(intl1;lk-1n;l){intminvINT_MAX;for(intil;ilk-1;i)minvmin(minv,a[i]);coutminv ;}像这样直接去遍历无疑 肯定是会超限的 那么就应该需要去优化了 也就是 滑动窗口 去维护一段区间 再借助单调队列 去维护区间内的最值for(ll i1;in;i){while(hta[q[t]]a[i]){t--;}q[t]i;while(q[h]i-k1){h;}if(ik){couta[q[h]] ;}}在维护区间最小值时 维护队列内下标对应的数值 单调递增核心1.去队尾维护单调性在向队列内加入新元素时如果队尾元素对应的数值 新加入的下标对应的数值 说明队尾旧元素不可能成为后续窗口最小值直接弹出队尾直到队尾数值新加入的数值即新加入的数值永远不可能成为最小值再把i入队2.队头剔除越界元素若队头下标不在当前窗口范围 i-k1队头下标i就从队头弹出此时队头就是当前窗口最小值的下标。代码实现#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second using namespace std; int main() { IOS ll k,n; ll h,t; cinnk; vectorlla(n5); vectorllq(n5); for(int i1;in;i) { cina[i]; } h1;t0; for(ll i1;in;i) { while(hta[q[t]]a[i]) { t--; } q[t]i; while(q[h]i-k1) { h; } if(ik) { couta[q[h]] ; } } coutendl; h1;t0; for(ll i1;in;i) { while(hta[q[t]]a[i]) { t--; } q[t]i; while(q[h]i-k1) { h; } if(ik) { couta[q[h]] ; } } // coutfixedsetprecision(x) ; return 0; }[P2058 NOIP 2016 普及组] 海港 - 洛谷# P2058 [NOIP 2016 普及组] 海港涉及点 滑动窗口普通队列解题过程已经知道t是严格升序 题目给出船只到达时间 t 单调递增采用滑动窗口 普通队列实现队列queue先进先出 将t 与 国籍x捆绑到一起(利用结构体)q.push({t,x});先用 cnt 记录当前窗口内国籍 x 的乘客数量kind 存窗口内不同国籍总数若入队前 cnt[x]0说明是新增国籍kind 执行 cnt[x]然后入队完成后 通过一个while循环去清理过期乘客 ti - 86400 tp ti利用滑动窗口去查 while(!q.empty()q.front().tt-N)若队首乘客满足 q.front().t ≤ t - 86400 表示超出 24 小时窗口 取出队首国籍 xx cnt[xx]–若 cnt[xx]0窗口内不存在该国籍kind-- 弹出队首代码实现//P2058 #includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second using namespace std; const int N86400; const int M1e55; struct ship{ ll t; ll x; }; ll cnt[M]; int main() { IOS ll n; cinn; queueshipq; ll kind0; for(ll i1;in;i) { ll t,x; ll k; cintk; for(ll j1;jk;j) { cinx; q.push({t,x}); if(!cnt[x]) { kind; } cnt[x]; } while(!q.empty()q.front().tt-N) { ll xxq.front().x; cnt[xx]--; if(!cnt[xx])kind--; q.pop(); } coutkindendl; } // coutfixedsetprecision(x) ; return 0; }P1714 切蛋糕 - 洛谷P1714 切蛋糕涉及 前缀和 单调队列 滑动窗口最值不定长区间解题过程由题目可以看出是 找最大区间和6 31 -2 3 -4 5 -6 a[i]1 -1 2 -2 3 -3 sum[i]起点i为4时(1km)1 -2 3 (-4) 5 -6 a[i]k1 结果为sum[i]-sum[i-1]-41 -2 (3 -4) 5 -6 a[i]k2 结果为sum[i]-sum[i-2]-11 (-2 3 -4) 5 -6 a[i]k3 结果为sum[i]-sum[i-3]-3…km 结果为sum[i]-sum[i-m]sum[R]-sum[L-1] 区间长度为 1R-L1msum[i]-sum[l] 假定lL-1 1i-lm即区间范围 i-mli-1ansmax(sum[i]-sum[l]) (i-mli-1)等价于anssum[i]-min(sum[l]) 暴力 解题范围太大超限写过上面两道题之后 可以说 找最值 肯定还是单调队列滑动窗口最快了找最大值 -单调队列滑动窗口-用一个queue去存下标代码实现//P1714 #includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second using namespace std; ll ans-233333333; int main() { IOS ll n,m; cinnm; vectorllp(n3); vectorllsum(n10); dequellq; for(ll i1;in;i) { cinp[i]; sum[i]sum[i-1]p[i]; } q.push_back(0);// 初始放入下标0sum[0]0作为起点 for(ll i1;in;i) {//移除队头 下标超出i-m范围长度超过m while(q.front()mi) // while (!(li-m)) { q.pop_front(); } //sum[i] - 最小sum[q.front()] ansmax(ans,sum[i]-sum[q.front()]); //维护单调递增队列队尾前缀和 当前sum[i]就弹出 找最小值 while(!q.empty()sum[q.back()]sum[i]) { q.pop_back(); } q.push_back(i); } coutansendl; // coutfixedsetprecision(x) ; return 0; }
