双端队列 HDOJ 3530 Subsequence

 

题目传送门

题意：问最长子序列，满足区间最大值 - 最小值在[m, k]之间

分析：用双端队列维护最大值和最小值，保存的是位置。当满足条件时，更新最大值。

/************************************************ * Author :Running_Time * Created Time :2015/9/25 星期五 08:50:32 * File Name :A_deque.cpp************************************************/#include <cstdio> #include <algorithm> #include <iostream> #include <sstream> #include <cstring> #include <cmath> #include <string> #include <vector> #include <queue> #include <deque> #include <stack> #include <list> #include <map> #include <set> #include <bitset> #include <cstdlib> #include <ctime> using namespace std;#define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1 typedef long long ll; const int N = 1e5 + 10; const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; const double EPS = 1e-8; int a[N];int main(void) {int n, m, k;while (scanf ("%d%d%d", &n, &m, &k) == 3) {deque<int> Q1, Q2;int ans = 0, l = 1;for (int i=1; i<=n; ++i) {scanf ("%d", &a[i]);while (!Q1.empty () && a[Q1.back ()] <= a[i]) Q1.pop_back ();Q1.push_back (i);while (!Q2.empty () && a[Q2.back ()] >= a[i]) Q2.pop_back ();Q2.push_back (i);while (!Q1.empty () && !Q2.empty () && a[Q1.front ()] - a[Q2.front ()] > k) {if (Q1.front () < Q2.front ()) {l = Q1.front () + 1; Q1.pop_front ();}else {l = Q2.front () + 1; Q2.pop_front ();}}if (!Q1.empty () && !Q2.empty () && a[Q1.front ()] - a[Q2.front ()] >= m) {if (ans < i - l + 1) ans = i - l + 1;}}printf ("%d\n", ans);}return 0; }

 

数组模拟：

/************************************************ * Author :Running_Time * Created Time :2015/9/22 星期二 15:49:25 * File Name :A.cpp************************************************/#include <cstdio> #include <algorithm> #include <iostream> #include <sstream> #include <cstring> #include <cmath> #include <string> #include <vector> #include <queue> #include <deque> #include <stack> #include <list> #include <map> #include <set> #include <bitset> #include <cstdlib> #include <ctime> using namespace std;#define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1 typedef long long ll; const int N = 1e5 + 10; const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; const double EPS = 1e-8; int dq1[N], dq2[N], a[N];int main(void) {int n, m, k;while (scanf ("%d%d%d", &n, &m, &k) == 3) {for (int i=1; i<=n; ++i) {scanf ("%d", &a[i]);}int f1 = 0, f2 = 0, b1 = 0, b2 = 0, l = 1;int ans = 0;for (int i=1; i<=n; ++i) {while (f1 < b1 && a[dq1[b1-1]] <= a[i]) b1--;dq1[b1++] = i;while (f2 < b2 && a[dq2[b2-1]] >= a[i]) b2--;dq2[b2++] = i;while (f1 < b1 && f2 < b2 && a[dq1[f1]] - a[dq2[f2]] > k) {if (dq1[f1] < dq2[f2]) {l = dq1[f1++] + 1;}else l = dq2[f2++] + 1;}if (f1 < b1 && f2 < b2 && a[dq1[f1]] - a[dq2[f2]] >= m) {ans = max (ans, i - l + 1);}}printf ("%d\n", ans);}return 0; }

　　

转载于:https://www.cnblogs.com/Running-Time/p/4837447.html

总结

以上是生活随笔为你收集整理的双端队列 HDOJ 3530 Subsequence的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。