蓝桥杯大赛--游园安排解析

二分求最长上升子序列板子题,我们可以发现二分求得的最长上升队列中,保存的就是当前长度最小的数字,因此我们只需要每覆盖一个存储它们前面一个,最后递归输出。

import java.util.Scanner;
public class Main05 {
    public static int N= 1000010;
    public static String[]A = new String[N];
    public static String s =new String();
    public static String ans=new String();
    public static int [] q =new int[N];
    public static int [] pre =new int[N];
    public static int cnt;

    public static void dfs(int u)
    {
        if(u ==0){
            return;
        }
        dfs(pre[u]);
        ans+=A[u];
    }
    public static void init()
    {
        int len =s.length();
        for (int i=0,j=0;i<len;i++)
        {
            if (s.charAt(i)>='A'&&s.charAt(i)<='Z')
            {
                j=i;
                while (j+1<len&&s.charAt(j+1)>='a'&&s.charAt(j+1)<='z'){
                    j++;
                }
                if(j-i+1<0){
                    A[++cnt] = s.substring(i);
                }
                else {
                    A[++cnt] = s.substring(i,j+1);
                }
                i =j;
            }
        }
    }
    public static void solve()
    {
        int len =0;
        for (int i =1;i<=cnt;i++){
            int l =0,r =len;
            while (l<r){
                int mid = l+r+1>>1;
                if(A[q[mid]].compareTo(A[i])<0) l =mid;
                else r =mid -1;
            }
            q[r+1] =i;
            pre[i]=q[r];
            len =Math.max(r+1,len);
        }
        int idx =q[len];
        dfs(idx);
        System.out.println(ans);
    }

    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);//woAiLanQiaoBei
        s =sc.nextLine();
        init();
        solve();
    }
}