[贪心]Two Merged Sequences(CF-1144

传送门

Two Merged Sequences

AC代码

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN = 2e5+10;
int a[MAXN];
int up[MAXN], down[MAXN], flag[MAXN];
int high = -1;
int low = 0x3f3f3f;
int len1 = 0, len2 = 0;
int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    for(int i = 0; i < n; i++){
        
        if(a[i] > high && a[i] < low){
            if(a[i+1] > a[i]){ 
                up[++len1] = a[i];
                high = a[i];
                flag[i] = 0;
            }else{
                down[++len2] = a[i];
                low = a[i];
                flag[i] = 1;
            }
        }
        else if(a[i] > high){
            up[++len1] = a[i];
            high = a[i];
            flag[i] = 0;
        }else if(a[i] < low){
            low = a[i];
            down[++len2] = a[i];
            flag[i] = 1;
        }else{
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    for(int i = 0; i < n; i++){
        cout << flag[i] << " "; 
    }
    cout << endl;
}