竞赛讨论区 > 牛牛的数列
头像
月が綺麗だ
发布于 2021-01-13 11:56
+ 关注

牛牛的数列

/*
算法思想:
使用数列arr={7 2 3 1 5 6}为例,
假设所求最长长度为max
1.先将数列分为一系列有序子序列,对应例子为{7}, {2,3},{1,5,6},
2.然后遍历一遍这些子序列,对于任意两个序列的首尾元素,判断:当去掉前一个序列的尾元素时或者去掉后一个序列的首元素时,
两个序列能否拼成严格递增的数列,如果可以,那么max = (length(前一序列) + length(后一序列), max)

实际的做法:
对于数组arr的每个元素,都记录了值,相同序列标记flag(用来标记是否同一序列,其实有点多余,不过我是为了方便而这么做),
从此处开始的顺序子序列的最长长度start_count, 从此处结束的顺序子序列最长长度end_count
1.先遍历一遍数组arr,填充arr每个元素的val, start_count, end_count,这样就将整个序列分为若干个有序序列了
2.一次遍历,更新max的值,即结束
*/



#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
typedef unsigned int uint;
struct node{
    uint val; //数列的值
    uint flag;//辅助作用,为每个顺序子序列作标记,每个顺序子序列有一个唯一标志
    uint start_count; //从此处开始的顺序子序列的最大长度
    uint end_count;//从此处结束的顺序子序列的最大长度
};//arr每个元素对应要记录的数据
node arr[100005]; //由于n <= 100000,为了方便直接申请足够的空间

int main(){
    uint n;
    cin >> n;
    if(!n){ //处理边界情况
        cout << 0;
        return 0;
    }
    else if(n == 1){ //处理边界情况
        cout << 1;
        return 0;
    }
    uint temFlag = 0; //方便标志顺序子序列
    cin >> arr[0].val; //先处理首元素
    arr[0].flag = temFlag++; //先处理首元素
    for(int i = 1;i < n;i++){
        cin >> arr[i].val;
        if(arr[i - 1].val < arr[i].val){ //如果此元素跟上一个元素同属一个顺序子序列,那么有相同的标志
            arr[i].flag = arr[i - 1].flag;
        }
        else{ //此元素跟上一个元素属于不同的顺序子序列时
            arr[i].flag = temFlag++; //赋予新的标志
            
            //是时候来对上一个顺序子序列的元素的start_count,end_count进行记录了
            int j = i - 1;
            for(;j >= 0;j--){ //找到上一个顺序子序列的范围
                if(arr[j].flag != arr[i - 1].flag)
                    break;
            }
            j++; //已找到上一个顺序子序列的范围,为j<=k<=i-1
            for(int k = j;k <= i - 1;k++){
                arr[k].start_count = i - k;
                arr[k].end_count = k - j + 1;
            }
        }
    }
    
    //循环结束后,还有最后一个顺序子序列还没处理,所以要在这里进行处理
    int j = n - 1;
    for(;j >= 0;j--){
        if(arr[j].flag != arr[n - 1].flag)
            break;
    }
    j++;
    for(int k = j;k <= n - 1;k++){
        arr[k].start_count = n - k;
        arr[k].end_count = k - j + 1;
    }
    //最后一个顺序子序列已经处理
    
    /*再进行一次遍历,更新max的值就可以了,我在这里对每一个元素都处理了,其实没这个必要,实际上只需要对每个顺序子序列的首尾元素进行处理
    就可以了*/
    int tem = 0;
    int ans = 0;
    for(int i = 0;i < n;i++){
        if(!i && i + 1 < n){ //对于首元素
            tem = 1 + arr[i + 1].start_count;
        }
        else if(i && i + 1 < n){ //对于中间元素
            if(arr[i - 1].val < arr[i + 1].val){
                tem = arr[ i - 1].end_count + 1 + arr[i + 1].start_count;
            }
            else  
                tem = max(arr[i - 1].end_count + 1, arr[i + 1].start_count + 1);
        }
        else //对于尾元素
            tem = arr[i - 1].end_count + 1;
        if(tem > ans){
            ans = tem;
        }
    }
    cout << ans; //输入答案
    return 0;
}

全部评论

(0) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐