企业官网建设流程全解析

涉及： 队列 单调队列 滑动窗口 单调队列：队尾进队出队 队头 出队 前提：单调 (快速获取最大值最小值) 滑动窗口：维护一段连续区间 定长 区间长固定 +不定长 区间长度动态变化

P1886 【模板】单调队列 / 滑动窗口

涉及；单调队列+滑动窗口+定区间

解题过程

其实这个模板题是第二次看了 但是还是刚看到题目 之后 还是蛮模糊的
平时看到数组内求什么最大值 最小值都是暴力直接循环

for(intl=1;l+k-1<=n;l++){intminv=INT_MAX;for(inti=l;i<=l+k-1;i++)minv=min(minv,a[i]);cout<<minv<<" ";}

像这样直接去遍历无疑 肯定是会超限的 那么就应该需要去优化了 也就是 滑动窗口 去维护一段区间 再借助单调队列 去维护区间内的最值

for(ll i=1;i<=n;i++){while(h<=t&&a[q[t]]>a[i]){t--;}q[++t]=i;while(q[h]<i-k+1){h++;}if(i>=k){cout<<a[q[h]]<<" ";}}

在维护区间最小值时 维护队列内下标对应的数值 单调递增
核心：1.去队尾维护单调性：在向队列内加入新元素时，如果队尾元素对应的数值 >=新加入的下标对应的数值 说明队尾旧元素不可能成为后续窗口最小值，直接弹出队尾，直到队尾数值<新加入的数值，即新加入的数值永远不可能成为最小值，再把i入队；
2.队头剔除越界元素：若队头下标不在当前窗口范围 i-k+1<=队头下标<=i，就从队头弹出；此时队头就是当前窗口最小值的下标。

代码实现

#include<bits/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; cin>>n>>k; vector<ll>a(n+5); vector<ll>q(n+5); for(int i=1;i<=n;i++) { cin>>a[i]; } h=1;t=0; for(ll i=1;i<=n;i++) { while(h<=t&&a[q[t]]>a[i]) { t--; } q[++t]=i; while(q[h]<i-k+1) { h++; } if(i>=k) { cout<<a[q[h]]<<" "; } } cout<<endl; h=1;t=0; for(ll i=1;i<=n;i++) { while(h<=t&&a[q[t]]<a[i]) { t--; } q[++t]=i; while(q[h]<i-k+1) { h++; } if(i>=k) { cout<<a[q[h]]<<" "; } } // cout<<fixed<<setprecision(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().t<=t-N)
若队首乘客满足 q.front().t ≤ t - 86400 表示超出 24 小时窗口 取出队首国籍 xx cnt[xx]–
若 cnt[xx]==0，窗口内不存在该国籍，kind-- 弹出队首

代码实现

//P2058 #include<bits/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 N=86400; const int M=1e5+5; struct ship{ ll t; ll x; }; ll cnt[M]; int main() { IOS ll n; cin>>n; queue<ship>q; ll kind=0; for(ll i=1;i<=n;i++) { ll t,x; ll k; cin>>t>>k; for(ll j=1;j<=k;j++) { cin>>x; q.push({t,x}); if(!cnt[x]) { kind++; } cnt[x]++; } while(!q.empty()&&q.front().t<=t-N) { ll xx=q.front().x; cnt[xx]--; if(!cnt[xx])kind--; q.pop(); } cout<<kind<<endl; } // cout<<fixed<<setprecision(x)<< ; return 0; }

P1714 切蛋糕 - 洛谷

P1714 切蛋糕

涉及 前缀和 +单调队列+ 滑动窗口最值+不定长区间

解题过程

由题目可以看出是 找最大区间和
6 3
1 -2 3 -4 5 -6 a[i]
1 -1 2 -2 3 -3 sum[i]
起点i为4时(1<=k<=m)
1 -2 3 (-4) 5 -6 a[i]
k=1 结果为sum[i]-sum[i-1]=-4
1 -2 (3 -4) 5 -6 a[i]
k=2 结果为sum[i]-sum[i-2]=-1
1 (-2 3 -4) 5 -6 a[i]
k=3 结果为sum[i]-sum[i-3]=-3
…
k=m 结果为sum[i]-sum[i-m]
sum[R]-sum[L-1] 区间长度为 1<=R-L+1<=m
sum[i]-sum[l] 假定l=L-1 1<=i-l<=m
即区间范围 i-m<=l<=i-1
ans=max(sum[i]-sum[l]) (i-m<=l<=i-1)
等价于ans=sum[i]-min(sum[l]) 暴力 解题范围太大超限

写过上面两道题之后 可以说 找最值 肯定还是单调队列+滑动窗口最快了

找最大值 ->单调队列滑动窗口->用一个queue去存下标

代码实现

//P1714 #include<bits/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; cin>>n>>m; vector<ll>p(n+3); vector<ll>sum(n+10); deque<ll>q; for(ll i=1;i<=n;i++) { cin>>p[i]; sum[i]=sum[i-1]+p[i]; } q.push_back(0);// 初始放入下标0，sum[0]=0，作为起点 for(ll i=1;i<=n;i++) {//移除队头 下标超出i-m范围长度超过m while(q.front()+m<i) // while (!(l>=i-m)) { q.pop_front(); } //sum[i] - 最小sum[q.front()] ans=max(ans,sum[i]-sum[q.front()]); //维护单调递增队列：队尾前缀和 >= 当前sum[i]就弹出 （找最小值） while(!q.empty()&&sum[q.back()]>sum[i]) { q.pop_back(); } q.push_back(i); } cout<<ans<<endl; // cout<<fixed<<setprecision(x)<< ; return 0; }