美团笔试3.29：1，2题ac第3题超时

// 第一题
public class solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        for(int i = 0; i < t; i++){
            int n = scanner.nextInt();
            int k = scanner.nextInt();
            int sum = 0;
            for(int j = 0; j < n; j++){
                sum += scanner.nextInt();
            }
            if(sum <= n * k){
                System.out.println("YES");
            }else {
                System.out.println("NO");
            }
        }
    }
}

// 第二题
public static void main(String[] args) {
        // 不需要dp, 由中心往两边扩散。
        // 直接遍历长度为2的数组，如果其最大值不等于最小值则进入下一个
        // 或许可以在输入时确定当前前缀的后缀的0极差长度与值
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        for (int i = 0; i < t; i++) {
            int n = scanner.nextInt();
            int[] a = new int[2];
            // l存储当前前缀的后缀的最大极差长度
            int l = 1;
            int maxL = 1;
            for (int j = 0; j < n; j++) {
                a[j % 2] = scanner.nextInt();
                if(j>0 && a[j % 2] == a[(j-1) % 2]) {
                    l++;
                    if(l > maxL) maxL = l;
                }
                else l = 1;
            }
            System.out.println(n-maxL);
        }
    }

// 第三题
public class solution3 {

    public static int n;
    public static int x;
    public static int[] y;
    public static int[] m;
    public static int[][] a;
    public static int[][] b;

    public static double min = Double.MAX_VALUE;

    public static void main(String[] args) {
        // 关键在于n个图形间最小路径的构建
        // 空间复杂度较小，可以考虑回溯吗？
        // 最大时间复杂度约为7的7次方
        // 可以回溯
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        x = scanner.nextInt();
        y = new int[n];
        m = new int[n];
        // n个图形，每个图形有m[i]个点，a是第一个值，b是第二个值
        a = new int[n][];
        b = new int[n][];
        for(int i = 0; i < n; i++){
            y[i] = scanner.nextInt();
        }
        for(int i = 0; i < n; i++){
            m[i] = scanner.nextInt();
            a[i] = new int[m[i]];
            b[i] = new int[m[i]];
            for(int j = 0; j < m[i]; j++){
                a[i][j] = scanner.nextInt();
                b[i][j] = scanner.nextInt();
            }
        }

        double time =0;

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m[i]; j++){
                back(-1, 0, 0, 0);
            }
        }
        // 得到各节点之间最小距离，计算最小时间
        time += min/x;
        // 接下来计算各图形内部移动时间
        double sumdis = 0;
        double time_this = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m[i]-1; j++){
                sumdis += calDis(i, j, i, j + 1);
            }
            sumdis += calDis(i, 0, i, m[i]-1);
            time_this = sumdis / y[i];
            time += time_this;
        }
        System.out.println(time);
    }

    // 第i个图形, 中间距离， 上一个节点是第几个，头节点是第几个
    public static void back(int i, double mid, int last_node, int head_node){
        if(i > n){
            // 加上其与0的距离，记录最小路径
            mid += calDis_0(i-1, last_node);
            if(mid<min) min = mid;
            return;
        }
        for(int j = 0; j < m[i]; j++){
            if(i == 0){
                back(i+1, mid+calDis_0(i, j), j, j);
            }else {
                back(i+1, mid + calDis(i-1, last_node, i, j), j, head_node);
            }
        }
    }

    public static double calDis(int i, int j, int l, int k){
        return Math.pow((Math.pow((a[i][j] - a[l][k]), 2) + Math.pow((b[i][j] - b[l][k]), 2)), 0.5);
    }

    public static double calDis_0(int i, int j){
        return Math.pow((Math.pow((a[i][j]), 2) + Math.pow((b[i][j]), 2)), 0.5);
    }
}