最右10.22笔试

题目1

import java.util.Random;
import java.util.Scanner;

/**
 * @author wanna
 * @version v1.0
 * @Package com.wanna.main45
 * @date 2021/10/19 8:19 下午
 */
public class Main {
    /*
        @ 最右1
        找到一个数组中第一个缺少的正数
        比如arr=[-3,2,3]，缺少的第一个正数为1
        比如arr[-3,1,3]，缺少的第一个正数是2
     */

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = scanner.nextInt();
        }
        quickSort(arr);  // 先使用快排按照从小到大去进行排序
//        mergeSort(arr);

        // 如果最后一个元素都<=0，那么直接输出1
        if (arr[N - 1] <= 0) {
            System.out.println(1);
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            // 如果arr[i]<=0 并且arr[i+1]<=0，那么continue，还不是我们应该讨论的
            if (i + 1 < arr.length && arr[i] <= 0 && arr[i + 1] <= 0) {
                continue;
            }
            // 如果arr[i]<=0并且arr[i+1]>0，也就是先出现了负数(含0)，然后出现了正数
            // 需要讨论arr[i+1]是否为1，如果为1，continue，不是1直接输出1，因为一定缺少1
            if (i + 1 < arr.length && arr[i] <= 0 && arr[i + 1] > 0) {
                // 如果arr[i+1]是1的话，那么continue
                // 比如-2 1这种，因为下一个是1，不会缺少1，那么continue
                // 如果arr[i+1]不是1，比如-2 2，因为下一个是2，所以必然缺少1，进行输出
                if (arr[i + 1] == 1) {
                    continue;
                }
                // 如果这个元素不是1，那么输出1
                System.out.println(1);
                return;
            }
            // 如果arr[i]>0并且arr[i+1]>0，也就是两个正数的情况
            // 1.如果arr[i]==arr[i+1]，那么它之间并不缺少元素，continue
            // 2.如果arr[i]+1==arr[i+1]，之间也是不缺少元素，continue
            if (i + 1 < arr.length && arr[i] > 0 && arr[i + 1] > 0) {
                // 如果两者相等的话，那么continue
                // 如果当前元素+1=下一个元素，那么continue，因为之间不可能缺了元素
                if (arr[i] == arr[i + 1] || arr[i] + 1 == arr[i + 1]) {
                    continue;
                }
                System.out.println(arr[i] + 1);
                return;
            }
        }
        // 有可能一个数组中所有元素都为正数，有可能全部都为负数
        // 如果全部为负数，在上面已经处理过了，这里只需要处理全是正数并且不还不符合缺少了数的情况，需要输出arr[N-1]+1
        System.out.println(arr[N - 1] + 1);
    }

    public static void mergeSort(int[] arr) {
        mSort(arr, 0, arr.length - 1, new int[arr.length]);
    }

    public static void mSort(int[] arr, int left, int right, int[] temp) {
        if (right <= left) {
            return;
        }
        int mid = left + ((right - left) >> 1);
        mSort(arr, left, mid, temp);
        mSort(arr, mid + 1, right, temp);
        merge(arr, left, mid + 1, right, temp);
    }

    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int L = left, R = mid, index = L;
        for (; L < mid && R <= right; ) {
            temp[index++] = arr[L] > arr[R] ? arr[R++] : arr[L++];
        }
        for (; L < mid; ) {
            temp[index++] = arr[L++];
        }
        for (; R <= right; ) {
            temp[index++] = arr[R++];
        }
        System.arraycopy(temp, left, arr, left, right - left + 1);
    }

    public static void quickSort(int[] arr) {
        qSort(arr, 0, arr.length - 1);
    }

    public static void qSort(int[] arr, int left, int right) {
        if (right <= left) {
            return;
        }
        int random = left + new Random().nextInt(right - left + 1);
        swap(arr, random, right);
        int[] partition = partition(arr, left, right);
        qSort(arr, left, partition[0] - 1);
        qSort(arr, partition[1] + 1, right);
    }

    public static int[] partition(int[] arr, int left, int right) {
        int pivlot = arr[right];
        int less = left - 1;
        int more = right;
        for (; left < more; ) {
            if (arr[left] < pivlot) {
                swap(arr, left++, ++less);
            } else if (arr[left] > pivlot) {
                swap(arr, left, --more);
            } else {
                left++;
            }
        }
        swap(arr, right, more);
        return new int[]{less + 1, more};
    }

    public static void swap(int[] arr, int i, int j) {
        if (arr[i] == arr[j]) {
            return;
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}

题目2

import java.util.Scanner;

/**
 * @author wanna
 * @version v1.0
 * @Package com.wanna.main46
 * @date 2021/10/19 8:20 下午
 */
public class Main {
    /*
        @最右2 AC 80% TLE
        一共有N层
        第一行会输入N，代表学生的层数
        第二行会输入每一层的学生数量，比如[1,2,3]代表第一层有1个学生，第二层有2个学生，第三层有3个学生
        第二行之后会输入N行
        每一行的第一个数代表的是第i层的人向上走一层的体力消耗，每一行的第二个数代表第i层的人向下走一层的体力消耗
        如果走向上走j层/向下走j层，那么就得j*对应的体力消耗

        要选定一个k，代表最终要开会的层数，要求的是所有学生到k的体力消耗总数最小
        最终要输出的就是最小的消耗体力的数量
     */

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();  // 行数，也就是对应的行数
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = scanner.nextInt();  // 每一层的学生的个数
        }
        int[][] consume = new int[N][2];
        for (int i = 0; i < N; i++) {
            consume[i][0] = scanner.nextInt();  // 第i层的人向上走的一层单位体力消耗
            consume[i][1] = scanner.nextInt();  // 第i层的人向下走的一层单位体力消耗
        }
        process(consume, arr, N);
    }


    // 可以向上走，可以向下走，求所有学生的最小的体力消耗
    // AC 80% 然后TLE(时间超出)了...整体时间复杂度在O(n^2)
    public static void process(int[][] consume, int[] arr, int N) {

        int min = Integer.MAX_VALUE; // 初始化一个min代表最终需要输出的最小体力消耗
        // 如果开会选在第i层的话，最后的总消耗是多少呢？
        for (int i = 0; i < N; i++) {
            int currentConsume = 0; // currentConsume代表选在i层开会最终的体力消耗

            // 在i层以上的学生走到第i层的最终总消耗
            for (int j = i + 1; j < N; j++) {
                // j-i获取的是第j层楼到第i层楼差了几层楼
                // consume[j][1]也就是1个人向下走1层需要进行的消耗
                // arr[j]代表的是第j层的学生消耗体力的数量
                currentConsume += (j - i) * consume[j][1] * arr[j];
            }

            // 在i层以下的学生走到第i层的最终总消耗，分析过程和在i层以上的学生走到第i层的最终总消耗完全类似
            for (int j = i - 1; j >= 0; j--) {
                currentConsume += (i - j) * consume[j][0] * arr[j];
            }
            // 如果选用当前i层的最终消耗比以前的消耗低了，那么就得更新最终的结果
            min = Math.min(currentConsume, min);
        }
        System.out.println(min);
    }
}

#最右笔试##笔经##最右#