HDU杭电 3530 (FJUT 1920) Subsequence 单调栈

Problem Description
There is a sequence of integers. Your task is to find the longest subsequence that satisfies the following condition: the difference between the maximum element and the minimum element of the subsequence is no smaller than m and no larger than k.
注意这题题目描述不严谨,准确来说不是子序列,应该是子区间

Input
There are multiple test cases.
For each test case, the first line has three integers, n, m and k. n is the length of the sequence and is in the range [1, 100000]. m and k are in the range [0, 1000000]. The second line has n integers, which are all in the range [0, 1000000].
Proceed to the end of file.

Output
For each test case, print the length of the subsequence on a single line.

SampleInput
5 0 0
1 1 1 1 1
5 0 3
1 2 3 4 5

SampleOutput
5
4

这题题意很明了,就是维护单调栈,最终求得一个最长的、符合区间最大值和最小值的差值在[m,k]范围内条件的子序列。
我写这种基础题的题解,都是为了更好地理解一个知识点,能够不结合实际问题理解算法的都是理论帝和模拟帝==,可惜在下是弟弟,老规矩,代码配注释。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
const int MAX=1e5+5;
typedef long long ll;
typedef unsigned long long ull;
int s[MAX];
int main()
{
  int n, m, k, i, j, ans;
  while (~scanf("%d%d%d", &n, &m, &k))
  {
    for (i=1; i<=n; i++)
      scanf("%d", &s[i]);
    ans = 0;
    int qa[n+5], qb[n+5];/// 分别用来记录区间最大值和区间最小值所在位置下标
    int ma=0, mi=0, top1=0, top2=0, last1=0, last2=0;
    for (i=1; i<=n; i++)
    { /// top初始化都为0,第一次for循环,条件top<m可以忽略不计。之后top指向的
      ///是当前符合条件或最接近符合条件的下标,不论是收缩区间后的结果还是还
      ///没有。所以把新元素推入栈的时候,一定要先保证新来的元素下标在top之后
      while (top1<ma&&s[i]>=s[qa[ma-1]])/// 维护qa栈首指向区间最靠后的(为了区
                                        ///间尽可能长)、最大元素的下标,将
        ma --;                          ///<=s[i]的栈首丢掉
      qa[ma++] = i;/// 把i推入栈qa,这时如果s[i]会更新区间最大值,那么它自然会
      			   ///被往前推,qb同理

      while (top2<mi&&s[i]<=s[qb[mi-1]])/// 维护qb栈首指向区间最靠后的、最小元
        mi --;                          ///素的下标,将>=s[i]的栈首丢掉
      qb[mi++] = i;/// 把i推入栈qb

      while (s[qa[top1]]-s[qb[top2]]>k)/// 因为差大于k了,一边收缩区间,一边取
        if (qa[top1]<qb[top2])         ///最靠前的下标,因为我们要的是最长区间
          last1 = qa[top1++];/// top1记得往后推,只要还在循环内就还不符合条件
        else
          last2 = qb[top2++];/// top2一样
/// 想要改变差值,只能把区间往后缩小,扩张区间只有可能让区间最大值更大、区间
///最小值更小,从而使得k不减反增。

      if (s[qa[top1]]-s[qb[top2]]>=m)       /// 符合>=m条件的话,更新ans的值,
        ans = max(ans, i-max(last1, last2));///last1和last2取最大是因为最新更新
                                            ///的区间左边界才是符合上面<=k循环
                                            ///的结果
    }
    printf("%d\n", ans);
  }
  return 0;
}

上一篇:[社群QA] “专家坐诊”第17期问答汇总


下一篇:git 语句的使用