美团 8.26 笔试

只做出了三道半。。。感觉美团换成牛客平台后，特别针对Java选手，同样的思路cpp、py都能过。。。

第一题：小美种果树

当时直接模拟就好了，我在这边找规律，做了快半个小时

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        int z = sc.nextInt();
        int yu = z%(3*x+y); //一个周期三天 成长值3*x+y ,
        int ans =0;
        if(yu==0) {
            ans = 3* (z/(3*x+y));
        }else {
            if(yu<x+y){
                ans = 3* (z/(3*x+y))+1;
            }
            else if(yu<2*x+y){
                ans = 3* (z/(3*x+y))+2;
            }else {
                ans = 3* (z/(3*x+y))+3;
            }
        }
        System.out.println(ans);
    }

第二题：小美结账

直接模拟

 public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        long a[] = new long[m + 2];

        for (int i = 1; i <= n; i++){
            int k = sc.nextInt();
            int c = sc.nextInt();
            int avg = (c+k-1)/k;//向上取整
            for (int j = 1; j <= k-1; j++){
                int id = sc.nextInt();
                a[id] += avg;
            }
        }
        for (int i = 1; i <= m; i++){
            if(i==1){
                System.out.print(a[i]);
            }else {
                System.out.print(" ");
                System.out.print(a[i]);
            }
        }
        System.out.println("");
    }

第三题：小美的游戏

小美有一个长度为n的数组，她最多可以进行k次操作，每次操作如下：

1. 选择两个整数i,j(1<=i<j<=n)
2. 选择两个整数x,y，使得x*y=ai*aj
3. 将ai替换为x，将aj替换为y

她希望最多进行k次操作之后，最后数组中的元素的总和尽可能大。

思路：堆模拟。找到堆中最大的两个元素相乘，再往堆里加入相乘的值和1，循环k次即可。

static final int MOD = (int) 1e9 + 7;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        PriorityQueue<BigDecimal> pq = new PriorityQueue<>((a, b) -> b.compareTo(a));
        for (int i = 0; i < n; i++) {
            long x = sc.nextInt();
            pq.offer(BigDecimal.valueOf(x));
        }
        BigDecimal ans = BigDecimal.valueOf(0);
        while (k-- > 0) {
            BigDecimal x = pq.poll(), y = pq.poll();
            pq.offer(x.multiply(y));
            pq.offer(BigDecimal.valueOf(1));
        }
        while (!pq.isEmpty()) {
            ans = ans.add(pq.poll());
        }
        System.out.println(ans.divideAndRemainder(BigDecimal.valueOf(MOD))[1]);
    }

第四题：小美的数组重排

小美有两个长度为n的数组a和b。

小美想知道，能不能通过重排a数组使得对于任意1<=i<=n,1<=ai+bi<=m？

将会有q次询问。

思路：要想满足题目的要求，对于数组a的最小值，如果跟数组b的最大值进行合并，假设结果不满足，那就肯定是不可能的了，否则可以考虑次小值和次大值进行分配，以此类推，只需要将a数组正向排序，b数组逆向排序即可。

static final int N = 510;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int q = sc.nextInt();
        while (q-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[] a = new int[n];
            int[] b = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }
            for (int i = 0; i < n; i++) {
                b[i] = sc.nextInt();
            }
            Arrays.sort(a);
            Arrays.sort(b);
            boolean flag = true;
            for (int i = 0, j = n - 1; i < n; i++, j--) {
                if (!(a[i] + b[j] >= 1 && a[i] + b[j] <= m)) {
                    flag = false;
                    break;
                }
            }
            System.out.println(flag ? "YES" : "NO");
        }
    }

第五题：平均数为k的最长连续子数组

给定n个正整数组成的数组，求平均数正好等于k 的最长连续子数组的长度。

如果不存在任何一个连续子数组的平均数等于k，则输出-1。

否则输出平均数正好等于k的最长连续子数组的长度。

思路：思维题+哈希表模拟。

平均数比较难处理，我们不妨将原数组中每个元素都-k，这样问题转换成找到和为0的最长子数组。

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] a = new int[n];

        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt() - k;
        }

        int res = 0;
        HashMap<Integer, Integer> occ = new HashMap<>();
        occ.put(0, -1);
        int tmp = 0;
        for (int i = 0; i < n; i++) {
            tmp += a[i];
            if (occ.containsKey(tmp)) {
                res = Math.max(res, i - occ.get(tmp));
            }
            if (!occ.containsKey(tmp)) {
                occ.put(tmp, i);
            }
        }
        System.out.println(res);
    }