Codeforces Round #555 (Div. 3), problem: (C2) Increasing Subsequence (hard version)【贪心+撞到南墙也不回头】

题目链接

---

题目大意

复杂版大意是我们可以从左右两端每次拿走一个数，一直拿，不过要满足一个条件，每次拿的数要保证严格递增（即从小到大然后不会有相同的情况） 复杂版的话是会有相同的数字出现 在题解中正式说明

(C1) Increasing Subsequence (easy version) 博客地址

---

题解

在C1简易版已经把题意说的比较清楚了，对于复杂版的，我们就是在简易版加一条if语句，如果遇到了相同的值，那么我们就跳出循环，进行下一步比较

起初，对于相同的值那个点，我刚开始以为会有很多次这样的临界情况，然后要各种分析讨论，后面队友一下点醒了我，我们只要遇到了相同的数字，那么我们以后的方向就只有一种情况了，要么往左走到底，要么往右走到底，也就是标题所说：“撞到南墙也不回头!”

从下面代表即可看出，遇到相同的数字时，我们直接跳出简单版内的循环，然后我们通过两次遍历，从左游标到末尾，从右游标到头，然后找出长度最长的 （必须保证严格递增）

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int a[maxn],n;
string s="";
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int i=1,j=n;
    int tmp=0;
    while(i<=j){
        if(a[i]==a[j]) break;
        else if(min(a[i],a[j])>tmp){
            if(a[i]<a[j]){
                tmp=a[i];
                i++;
                s+="L";
            }else{
                tmp=a[j];
                j--;
                s+="R";
            }
        }
        else if(max(a[i],a[j])>tmp){
            if(a[i]>a[j]){
                tmp=a[i];
                i++;
                s+="L";
            }else{
                tmp=a[j];
                j--;
                s+="R";
            }
        }

        else break;
    }
    //cout<<tmp<<endl;
    if(a[i]==a[j]){
        int tmp1=tmp;
        int tmp2=tmp;
        int le=0;
        for(int k=i;k<=n;k++){
            if(a[k]>tmp1){
                tmp1=a[k];
                le++;
            }
            else break;
        }
        int re=0;
        for(int k=j;k>=1;k--){
            if(a[k]>tmp2){
                tmp2=a[k];
                re++;
            }
            else break;
        }
        if(le>re){
            while(le--) s+="L";
        }
        else{
            while(re--) s+="R";
        }
    }
    /*if(s.length()==0){
        cout<<1<<endl;
        cout<<"R"<<endl;
        return 0;
    }*/
    cout<<s.length()<<endl;
    cout<<s<<endl;
    return 0;
}

学如逆水行舟，不进则退