本文主要是介绍单调队列(专项复习)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
P1886 滑动窗口 /【模板】单调队列
题目思路:单调队列模版题,每次都输出队列中的第一个元素。以此维护队列中元素序号的单调性，得到结果。只是比较判断，时间复杂度很小。相等的值也要挤掉。最大值同理。
代码实现:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 3000005
ll dp[N], f1[N], f2[N];
ll a[N], b[N], c[N];
bool vis[N], flag;
ll x, y, z, n, m, t, k;
ll ans, sum, cnt;
deque<ll>q;
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = 1; i <= n; i++) {while (!q.empty() && a[q.back()] >= a[i]) q.pop_back();q.push_back(i);if (i >= m) {while (q.front() <= i - m) q.pop_front();cout << a[q.front()] << " ";}}cout << endl;q.clear();for (int i = 1; i <= n; i++) {while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();q.push_back(i);if (i >= m) {while (q.front() <= i - m) q.pop_front();cout << a[q.front()] << " ";}}return 0;
}P1901 发射站
题目思路: 用一个线性算法，先从左往右推。若在栈中栈顶那个塔的高度比当前塔的高度低，即此塔为栈顶塔右边的第一个比栈顶塔高的塔，那么栈顶塔的能量就要加给当前塔，然后将队列顶塔出栈。直到队列内无塔或下一塔比它的高度高，就将该塔进队列，并指向下一个塔。反之亦然。两趟之间要清空栈，最后再打个擂台，找MAX。
代码实现:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 3000005
ll dp[N], f1[N], f2[N];
ll a[N], b[N], c[N];
bool vis[N], flag;
ll x, y, z, n, m, t, k;
ll ans, sum, cnt;
deque<ll>q;
struct node {ll x, y, z;
}f[N];
int main()
{cin >> n;for (int i = 1; i <= n; i++)cin >> f[i].x >> f[i].y;for (int i = 1; i <= n; i++) {while (!q.empty() && f[q.back()].x < f[i].x) {f[i].z += f[q.back()].y;q.pop_back();}if (!q.empty()) {f[q.back()].z += f[i].y;}q.push_back(i);}for (int i = 1; i <= n; i++)ans = max(ans, f[i].z);cout << ans << endl;return 0;
}P1419 寻找段落
题目思路:
首先看出答案满足单调性，可以二分答案，转化为判定性问题。令最优平均值为k,对于所有合法序列[l..r],尝试将分式变为整式：s[l..r]＞k*(r-l+1)无解。移项，令b[i]=a[i]-k，s’[i]为b[1]..b[n]的和，则有寻找长度在[s,t]内的子段和的最大值可以用单调队列解决
代码实现:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 3000005
ll dp[N], f1[N], f2[N], a[N];
double b[N], c[N];
bool vis[N], flag;
ll x, y, z, n, m, t, k;
ll sum, cnt;
double l, r, mid, ans;
deque<ll>q;bool check(double k) {q.clear();for (int i = 1; i <= n; i++)c[i] = (double)a[i] - k;for (int i = 1; i <= n; i++) {b[i] = b[i - 1] + c[i];}for (int i = 1; i <= n; i++) {if (i >= x) {while (!q.empty() && b[q.back()] > b[i - x]) q.pop_back();q.push_back(i - x);}if (!q.empty() && i - y > q.front()) q.pop_front();if (!q.empty() && b[i] - b[q.front()] >= 0) return true;}return false;
}
int main()
{cin >> n >> x >> y;for (int i = 1; i <= n; i++)cin >> a[i];l = -10000; r = 10000;while (r - l > 1e-5) {mid = (l + r) /2;if (check(mid))ans = l = mid;elser = mid;}printf("%.3lf\n", ans);return 0;
}这篇关于单调队列(专项复习)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
