拼多多笔试

拼多多笔试0420

多多的游戏

贪心+多路选择

1. 对每个字符串 Si，提取其字符并按字典序排序，只保留前 Xi 个最小的字符。
2. 将所有保留的字符放到一个总候选池中。
3. 对这个大池子进行字典序排序，选前 K 个字符，拼成字符串 T。

import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int K = in.nextInt();
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < N; i++) {
            String s = in.next();
        	int x = in.nextInt();
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            sb.append(new String(chars, 0, x));
        }
        
        char[] candidates = sb.toString().toCharArray();
        Arrays.sort(candidates);
        String ans = new String(candidates, 0, K);
        System.out.println(ans);
    }
}

• 时间复杂度：假设读取的字符串平均长度之和为L，$O(L\cdotlogL)$。
• 空间复杂度：O(L)

多多的电影

拓扑排序

1. 图建模：

   • 将每个演员视为图中的一个节点。
   • 每条意见(ai, bi)表示一条有向边，从bi指向ai（表示ai片酬 > bi片酬）。

2. 拓扑排序检测是否有环：

   • 如果图中存在环，则说明存在矛盾意见（比如A > B, B > C, C > A），无法满足所有约束，输出-1。

3. 最小化总片酬：

   • 每位演员最少拿100元，调整是10元单位。
   • 将该问题看作在满足拓扑顺序的前提下，用最少的“级别”分配每个节点的权值。
   • 从入度为0的节点开始，进行拓扑排序，并将每个演员的片酬设置为满足约束所需的最小值。

import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for (int t = 0; t < T; t++) {
            int n = in.nextInt();
            int m = in.nextInt();
            // 定义图和入度、工资层级
            List<List<Integer>> graph = new ArrayList<>();
            int[] inDegree = new int[n + 1];
            int[] salaryLevel = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                graph.add(new ArrayList<>());
            }
            // 建图
            for (int i = 0; i < m; i++) {
                int a = in.nextInt();
                int b = in.nextInt();
                graph.get(b).add(a);
                inDegree[a]++;
            }
            // 拓扑排序
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 1; i <= n; i++) {
                if (inDegree[i] == 0) {
                    queue.offer(i);
                }
            }
            int cnt = 0;
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                cnt++;
                for (int nxt : graph.get(cur)) {
                    if (salaryLevel[nxt] < salaryLevel[cur] + 1) {
                        salaryLevel[nxt] = salaryLevel[cur] + 1;
                    }
                    if (--inDegree[nxt] == 0) {
                        queue.offer(nxt);
                    }
                }
            }
            
            // 存在环
            if (cnt != n) {
                System.out.println(-1);
            } else {
                long total = 0L;
                for (int i = 1; i <= n; i++) {
                    total += 100 + 10 * salaryLevel[i];
                }
                System.out.println(total);
            }
        }
    }
}

• 时间复杂度：O(m+n)
• 空间复杂度：O(m+n)

多多的音乐节

贪心 + 二分查找

在原序列中，找到最长的严格递增子序列（LIS），最少调整的点数 = n - LIS长度。

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for (int t = 0; t < T; t++) {
            int n = in.nextInt();
            int[] heights = new int[n];
            for (int i = 0; i < n; i++) {
                heights[i] = in.nextInt();
            }
            System.out.println(n - lengthOfLIS(heights));
        }
    }
    
    private static int lengthOfLIS(int[] nums) {
        int ng = 0; // g 的长度
        for (int x : nums) {
            int j = lowerBound(nums, 0, ng - 1, x); // 注意闭区间：传入 [0, ng-1]
            nums[j] = x;
            if (j == ng) { // 没有找到 >= x 的元素
                ng++;
            }
        }
        return ng;
    }

    // 闭区间写法
    private static int lowerBound(int[] nums, int left, int right, int target) {
        while (left <= right) { // 闭区间 [left, right]
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1; // 目标在右侧
            } else {
                right = mid - 1; // 目标在左侧或正好是 mid
            }
        }
        return left; // 最终 left 是第一个 >= target 的位置
    }
}

• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)