美团笔试 九月二号 分享一下后三题

第五题，给出一列数两两凑对能凑出多少不同的对，没思路用优先队列瞎写居然过了，有人能证明最优解吗

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        HashMap<Integer,Integer> map = new HashMap<>();
        int n = in.nextInt();
        in.nextLine();
        for(int i = 0;i < n;i++) {
            int t = in.nextInt();
            map.put(t,1 + map.getOrDefault(t,0));
        }
        int m = map.size();
        PriorityQueue<Integer> pq = new PriorityQueue<>(((o1, o2) -> (o2 - o1)));
        for(int e:map. values()){
            pq.offer(e);
        }
        int res = 0;

        while (!pq.isEmpty()){
            List<Integer> temp = new ArrayList<>();
            int cur = pq.poll();
            while (cur > 0 && !pq.isEmpty()){
                if(pq.size() == 1 && cur == 2) {
                    cur = 0;
                    res ++;
                    continue;
                }
                cur--;
                res++;
                int nxt = pq.poll() - 1;
                if(nxt > 0) temp.add(nxt);
                
            }
            if(pq.isEmpty() && cur >= 2) res ++;
            pq.addAll(temp);
        }
        System.out.println(res);


    }
}

第四题，给出n个数删除k个使得剩下的互相为倍数，动态规划

import java.util.Arrays;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt(),k = in.nextInt();
        in.nextLine();
        int[] nums = new int[n];
        for(int i = 0;i < n;i++) {
            nums[i] = in.nextInt();
        }
        Arrays.sort(nums);
        int mod = 1000000007;
        int res = 0;
        int[][] f = new int[n][n - k];
        for(int i = n - 1;i >= 0;i--){
            f[i][0] = 1;
            for(int j = i + 1;j < n;j++){
                if(nums[j] % nums[i] == 0) {
                    for(int p = 1;p <n - k;p++){
                        f[i][p] = (f[i][p] + f[j][p - 1]) % mod;
                    }
                }
            }
            res = (res + f[i][n - k - 1]) % mod;
        }
        System.out.println(res);

    }
}

第三题：给n个数，每次把一个数除2或把第一个数乘2，求让第一个数成为最大的最少操作数

import java.util.PriorityQueue;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        in.nextLine();
        int first = in.nextInt();
        if(n == 1) {
            System.out.println(0);
            return;
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>(((o1, o2) -> (o2 - o1)));
        for(int i = 1;i < n;i++) pq.offer(in.nextInt());
        int res = Integer.MAX_VALUE,cur = 0;
        while (cur < res){
            int p = pq.poll();
            res = Math.min(count(p,first) + cur,res);
            pq.offer(p / 2);
            cur++;
        }
        System.out.println(res);
    }
    public static int count(int t,int f){
        int res = 0;
        while (f < t){
            f *= 2;
            res ++;
        }
        return res;
    }
}