51nod选择子序列：单调栈 & 分治

1153 选择子序列 

题目来源： Codility

基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题

 收藏

 关注

长度为N的整数数组A，所有的数均不相同，假设下标从0开始。找到一个最长的数组B，B数组的长度为K，数值范围是0 - N - 1，记录的是A数组的下标。满足A[B[0]] > A[B[1]] > A[B[2]] >...A[B[K]]，并且对任意连续的两项B[i]及B[i + 1]，满足min(B[i]，B[i + 1]) < j < max(B[i]，B[i + 1]) 均有A[j] < A[B[i + 1]] ，求最大的K。例如：9, 10, 2, -1, 3, -5, 0, -3, 1, 12, 5, 8, -2, 6, 4。可以选出：12, 10, 3, 1, 0, -3。对应的下标为：9, 1, 4, 8, 6, 7（就是B数组），输出6。

Input

第1行：一个数N，表示A数组的长度。（1 <= N <= 50000)
第2 - N + 1行：每行1个数对应A数组的元素Ai（0 < Ai < 10^9)

Output

输出B数组最长的长度K。

Input示例

15
9
10
2
-1
3
-5
0
-3
1
12
5
8
-2
6
4

Output示例

6

李陶冶 (题目提供者)

C++ 11的运行时限为：1000 ms ，空间限制为：131072 KB 示例及语言说明请按这里

题意：找一个下降序列，要求相邻的两位满足题目的要求。

思路：显然，B数组第一个数是A数组的最大数下标，假如不是，将此下标放到B数组首位可以获得更优解。因此得出如下简单分治方法O(nlogn)，为什么不会超时呢？因为数据弱，没有单调递减的样例，并不会退化到O(n*n)。那如果数据加强了怎么办呢？显然可以用线段树或其他办法预处理出区间的最大值，递归时就无需每次都遍历了。另外的方法就是单调栈，我们预处理每个数左右最近的比自己大的数的下标l[i]和r[i]，留意到递归过程找到的分界点下标，i必然就是l[i]的右界和r[i]的左界，因此O(n)可以解决本题。

AC_1：

# include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4+30;
int h[maxn];
int solve(int l, int r)
{
    if(l>r) return 0;
    int id=0;
    for(int i=l; i<=r; ++i)
        if(!id||h[id]<h[i])
            id=i;
    return max(solve(l, id-1), solve(id+1, r))+1;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; ++i) scanf("%d",&h[i]);
    printf("%d\n",solve(1,n));
    return 0;
}

AC_2：

# include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4+30;
int l[maxn], r[maxn], L[maxn], R[maxn], a[maxn];
int q[maxn];
int solve(int l, int r, int cur)
{
    if(l>r) return 0;
    return max(solve(l, cur-1, L[cur]), solve(cur+1, r, R[cur]))+1;
}
int main()
{
    int n, cnt=0, id;
    scanf("%d",&n);
    for(int i=1; i<=n; ++i)
    {
        scanf("%d",&a[i]);
        if(i==1||a[id]<a[i]) id=i;
    }
    for(int i=1; i<=n; ++i)
    {
        while(cnt&&a[q[cnt]]<a[i]) --cnt;
        l[i] = cnt?q[cnt]:i;
        R[l[i]] = i;
        q[++cnt] = i;
    }
    cnt = 0;
    for(int i=n; i>=1; --i)
    {
        while(cnt&&a[q[cnt]]<a[i]) --cnt;
        r[i] = cnt?q[cnt]:i;
        L[r[i]] = i;
        q[++cnt] = i;
    }
    printf("%d\n",solve(1, n, id));
    return 0;
}