[Java知识库]Java第十二届蓝桥杯b组真题 双向排序

题目链接

import java.util.*;
public class Main {
    static int N = 100010;
    
    static CII stk[] = new CII[N];
    static int a[] = new int[N];
    static int top;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        while(m -- > 0) {
            int t = sc.nextInt();
            int x = sc.nextInt();
            if(t == 0) {
                while(top > 0 && stk[top].t == 0) x = Math.max(x, stk[top -- ].x);
                while(top >= 2 && stk[top - 1].x <= x) top -= 2;
                stk[ ++ top] = new CII(0, x);
            }
            else if(top != 0) {
                while(stk[top].t == 1) x = Math.min(x, stk[top -- ].x);
                while(top >= 2 && stk[top - 1].x >= x) top -= 2;
                stk[ ++ top] = new CII(1, x);
            }
        }
        
        int l = 1, r = n, k = n;
        for(int i = 1; i <= top; i ++ ) {
            int x = stk[i].x;
            if(stk[i].t == 0) {
                while(r > x && l <= r) a[r -- ] = k -- ;
            } else {
                while(l < x && l <= r) a[l ++ ] = k -- ;
            }
            if(l > r) break;
        }
        
        if(top % 2 == 1)
            while(l <= r) a[l ++ ] = k -- ;
        else 
            while(l <= r) a[r -- ] = k -- ;
            
        for(int i = 1; i <= n; i ++ ) 
            System.out.print(a[i] + " ");
    }
    
    static class CII {
        int t, x;
        public CII(int a, int b) {
            t = a; x = b;
        }
    }
}