蓝桥杯2020年第十一届国赛真题-游园安排（JAVA题解）

解题思路:

提供了两种方法分别为solve1和solve2：

第一种是常规的LIS动态规划解法，时间复杂度为O(n^2)，只能过70%的测试点

第二种是使用贪心+二分思想优化的LIS解法，时间复杂度为O(nlogn)，可以AC

以上的两种解法这里不再赘述了

值得注意的是，

首先，本题需要比较的是字符串的大小，因此判断条件需要更换

其次，本题意在处理得到LIS的真正序列，而非仅仅得到LIS的长度

    所以，应当使用额外的变量或数组记录LIS序列的下标

        主要思路：从右至左遍历, 如果某元素在LIS序列中的位置不是其真正的位置, 那么一定有之前的元素下标大于该元素的下标（这里的下标都是针对LIS序列而言的），所以只要maxL未减小到真正的下标所对应的元素, 循环就会一直向下进行。

此外，使用StringBuffered存储会消耗更长的时间，建议换用数组存储。

参考代码:

import java.io.*;
import java.util.*;

// O(n^2)超时, 必须换用O(nlogn)求解最长上升子序列
// 本题除了求解LIS的长度以外, 还要额外求出LIS的序列, 因此需要额外的变量或数组记录下标
public class Main {
    static Scanner cin;
    static PrintWriter out;
    static String line;
    static StringBuffer[] values;

    public static void main(String[] args) throws IOException{
        cin = new Scanner(System.in);
        out = new PrintWriter(new OutputStreamWriter(System.out));
        line = cin.next();
        values = tokenizer(line);  // 获取名字
//        solve1();  // O(n^2)
        solve2(); // O(nlogn)
        out.flush();
        out.close();

    }

    static void solve1(){  // 常规LIS解法, 时间复杂度为O(n^2)
        int[] dp = new int[values.length];
        Arrays.fill(dp, 1);
        int pos = 0;
        int maxL = 0;
        for(int i = 1; i < values.length; i++){
            for(int j = 0; j < i; j++){
                if(values[j].toString().compareTo(values[i].toString()) < 0)  // 可上升
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            if(maxL <= dp[i]){
                maxL = dp[i];
                pos = i;  // 记录当前下标
            }
        }
        StringBuffer res = new StringBuffer();
        for(int i = pos; i >=0 ; i--){
            if(dp[i] == maxL){
                res.insert(0, values[i]);
                maxL--;
            }
        }
        out.println(res);
    }

    static void solve2(){  // 二分+贪心优化LIS, 时间复杂度为O(nlogn)
        StringBuffer[] dp = new StringBuffer[values.length];
        dp[0] = values[0];
        int[] pos = new int[values.length];  // 记录元素在dp数组下标
        int maxL = 1;
        for(int i = 1; i < values.length; i++){
            if(dp[maxL-1].toString().compareTo(values[i].toString()) < 0){  // 可上升
                dp[maxL++] = values[i];
                pos[i] = maxL-1;
            }else{
                int index = binarySearch(dp, 0, maxL-1, values[i]);
                dp[index] = values[i];  // 替换为更有潜力的新值
                pos[i] = index;
            }
        }
//        StringBuffer res = new StringBuffer();  // 使用StringBuffer会TLE
        ArrayList<String> res = new ArrayList<>();
        // 从右至左遍历, 如果某元素在dp数组中的位置不是其真正的位置, 那么一定有之前的元素下标大于该元素的下标
        // 所以只要maxL未减小到真正的下标所对应的元素, 循环就会一直向下进行
        for(int i = values.length-1; i >=0 ; i--){
            if(maxL < 0)
                break;
            if(pos[i] == maxL-1){
                res.add(values[i].toString());
                maxL--;
            }
        }
        for(int i = res.size()-1; i >= 0; i--)
            out.print(res.get(i));
//        out.println(res);
    }

    static int binarySearch(StringBuffer[] arr, int l, int r, StringBuffer value){  // 寻找插入位置
        int mid;
        while(l <= r){
            mid = (l+r) >> 1;
            int cmp = value.toString().compareTo(arr[mid].toString());
            if(cmp < 0)
                r = mid-1;
            else if(cmp > 0)
                l = mid+1;
            else
                return mid;
        }
        return l;
    }


    static StringBuffer[] tokenizer(String line){
        ArrayList<StringBuffer> list = new ArrayList<>();
        char[] cs = line.toCharArray();
        int size = -1;
        for(int i = 0; i < cs.length; i++){
            if(cs[i] <= 'Z' && cs[i] >= 'A'){
                size++;
                StringBuffer stb = new StringBuffer();
                stb.append(cs[i]);
                list.add(stb);
            }else{
                list.get(size).append(cs[i]);
            }
        }
        StringBuffer[] values = new StringBuffer[list.size()];
        return list.toArray(values);
    }
}