Codeforces-C1157 C2. Increasing Subsequence (hard version)
Also applies to easy versions
- 如果左边小于右边，把左边push进去，last等于左边，continue
- 如果右边小于左边，把右边push进去，last等于右边，continue
- 如果last大于等于左边，就看看右边最多能push进去几个，break
- 如果last大于等于右边，就看看左边最多能push进去几个，break
如果四个条件都不满足，说明此时左边等于右边并且都大于last。那么此时便出现了抉择，走左边长还是走右边长。
那么就可以用两个while分别跑左边和右边。如果满足递增顺序就将此种情况的最大长度加 1 。两个while跑完后，选择最长的那种情况。
Code
/**
* author: Akvicor
* created: 2019-07-19 19-30-49
**/
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
string to_string(string s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#endif
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 17
#endif
#ifdef DEBUG
#define FAST_IO 17
#else
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#endif
#define LL long long
#define ULL unsigned long long
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define reep(i, n) for(int i = 0; i <= (n); ++i)
#define lop(i, a, n) for(int i = a; i < (n); ++i)
#define loop(i, a, n) for(int i = a; i <= (n); ++i)
#define ALL(v) (v).begin(), (v).end()
#define PB push_back
#define VI vector<int>
#define PII pair<int,int>
#define FI first
#define SE second
#define SZ(x) ((int)(x).size())
const double EPS = 1e-6;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const LL LINF = 0x7f7f7f7f7f7f7f7f;
const int MAXN = (int)1e6 + 10;
const int MOD = (int)1e9 + 7;
int a[MAXN];
int main(){
FAST_IO;
int n;
cin >> n;
rep(i, n) cin >> a[i];
int last = -1, l = 0, r = n-1;
string ans;
while(l <= r){
if(last >= a[l]){
while(l <= r && last < a[r]){
ans.push_back('R');
last = a[r];
--r;
}
break;
}
if(last >= a[r]){
while(l <= r && last < a[l]){
ans.push_back('L');
last = a[l];
++l;
}
break;
}
if(a[l] < a[r]){
ans.push_back('L');
last = a[l];
++l;
continue;
}
if(a[r] < a[l]){
ans.push_back('R');
last = a[r];
--r;
continue;
}
int ll = 1;
while(ll < r-l+1 && a[l+ll] > a[l+ll-1]) ++ll;
int rr = 1;
while(rr < r-l+1 && a[r-rr] > a[r-rr+1]) ++rr;
if(ll >= rr) {
rep(i, ll) ans.push_back('L');
}else{
rep(i, rr) ans.push_back('R');
}
break;
}
cout << ans.size() << endl << ans << endl;
return 0;
}