考试平台： 牛客    时间： 2023-09-02    考试题型： 5道编程题 （每题 20 分）      T1 小美的升序数组（20分）   给定一个大小为n的数组a，请你判断一个数组是否满足以下条件:        数组严格升序，即  <  <...< 。     对于1 ≤ i ≤ n-1，我们定义 =  -  ，则数组b严格降序，即 >  > ... > 。      输入描述   第一行输入一个正整数n，代表数组的大小 第二行输入n个正整数a，代表给定的数组 3 ≤ n ≤  1 ≤  ≤    输出描述   若满足给定的两个条件，则输出 Yes。否则输出No   示例1   输入       3    1 3 4      输出       Yes      示例2   输入       3    1 3 3      输出       NO      示例3   输入       4    1 2 3 4      输出       NO      题解       简单模拟即可      import java.util.Scanner;public class Main {    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int n = scanner.nextInt();        int[] a = new int[n];        for (int i = 0; i < n; i++) a[i] = scanner.nextInt();        String rs = "YES";        for (int i = 1, prevB = Integer.MAX_VALUE; i < n; i++) {            int b = a[i] - a[i - 1];            if (a[i - 1] < a[i] && prevB > b) {                prevB = b;            } else {                rs = "NO";                break;            }        }        System.out.println(rs);    }}   T2 小美的子序列（20分）   小美在 n 行 m 列的本子上写了许多字母，她会在每一行中找出一个字母，然后组成一个字符串。 小美想知道，组成的字符串中是否存在至少一个字符串包含“meituan”子序列。   输入描述   第一行输入2个整数n,m (1 ≤ n,m ≤1000)。 接下来n行，每行输入一个长度为 m 的字符串表示小美写下的字母。   输出描述   若存在至少一个字符串包含"meituan"子序列，则输出"YES”，否则输出“NO”.   示例1   输入   3 3abcdefghi   输出   NO       显然并不能找到meituan子序列。      示例2   输入   8 2nmexittdulquacnt   输出   YES       第1行选择第2个字母    第2行选择第1个字母。    第3行选择第1个字母    第4行选择第1个字母    第5行选择第2个字母    第6行选择第2个字母    第7行选择第1个字母    第8行选择第1个字母组成字符串”meitluan”，其中存在"meituan"子序列。    当然，第6行选第1个字母且第5行选第1个字母组成的字符串"meituqan”中也存在"meituan"子序列。      题解       双指针      import java.util.Scanner;public class Main {    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int n = scanner.nextInt(), m = scanner.nextInt();        String[] words = new String[n];        for (int i = 0; i < n; i++) words[i] = scanner.next();        String rs = "meituan";        int len = rs.length(), idx = 0;        for (int i = 0; i < n && idx < len; i++) {            if (words[i].indexOf(rs.charAt(idx)) > -1) idx++;        }        System.out.println(idx == len ? "YES" : "NO");    }}       当然也可以使用动态规划去解。      public class Main {    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int n = scanner.nextInt(), m = scanner.nextInt();        String[] words = new String[n];        for (int i = 0; i < n; i++) words[i] = scanner.next();        String rs = "meituan";        int len = rs.length();        // dp[i][j] 为 true 表示前 rs[0, i) 在 words[0, j) 可以组成子序列        boolean[][] dp = new boolean[len + 1][n + 1];        dp[0][0] = true;        for (int i = 0; i < len; i++) {            char c = rs.charAt(i);            for (int j = 0; j < n; j++) {                dp[i + 1][j + 1] |= dp[i + 1][j];                if (words[j].indexOf(c) > -1 && dp[i][j]) {                    dp[i + 1][j + 1] = true;                }            }        }        System.out.println(dp[len][n] ? "YES" : "NO");    }}   T3 小美的数组（20分）   小美拿到了一个数组。她每次可以进行如下操作之一：        选择一个元素，使其乘以 2。     选择一个元素，使其除以 2，向下取整。      小美希望第一个元素变成所有元素的最大值。请你判断小美最少需要操作多少次?   输入描述   第一行输入一个正整数n，代表数组的大小。   第二行输入n个正整数，代表小美拿到的数组 1 ≤ n ≤  1 ≤  ≤    输出描述       输出最小操作次数。      示例1   输入   41 2 3 4   输