大厂真题 / 京东

京东 2026-9-5 笔试真题 - 研发岗

公式说明：数学公式保留为原始矢量图，避免抓取转换造成变量和约束缺失。

京东2026-9-5笔试真题 - 研发岗

题解整理了这场考试的完整题解和代码，希望能帮助大家更好地准备后续笔试。

本场考试概述

考试时间 ：2026年9月5日 考试岗位 ：研发岗 难度评级 ：中等偏难 考点分析 ：

• 第一题：排序 + 严格最长上升子序列（难度中等偏难）
• 第二题：切比雪夫转化（难度中等）

建议策略 ：

• 两道题的代码量都不大，真正吃时间的是判据推导。第一题务必先把”两人永不相遇”化成 $原题公式$ 这个只含起点终点的静态条件，再往 LIS 上靠；直接对着时间轴模拟必然写不出来。
• 第二题看到”曼哈顿距离最大”就该条件反射地想到 $原题公式$ 、 $原题公式$ 的切比雪夫转化，把两个绝对值解耦成两个一维极差问题， $原题公式$ 一趟扫完。
• 两题都是多组测试且总量到 $原题公式$ 量级，读写务必走缓冲 IO，否则算法对了也会 TLE。

第一题：不相遇的最多人数

题目描述

有 $原题公式$ 名成员站在一条直线上。第 $原题公式$ 个人的初始位置为 $原题公式$ ，目标位置为 $原题公式$ 。从时刻 $原题公式$ 开始，每个被选中的人会同时行动，规则如下：如果他还没到达目标位置，就以速度 $原题公式$ 沿直线朝着目标位置移动（也就是每经过 $原题公式$ 秒，走过的路程为 $原题公式$ ）；当他到达目标位置 $原题公式$ 后，就停在 $原题公式$ 不再移动。位置与时间都按实数理解（例如， $原题公式$ 秒也是允许讨论的时刻）。如果存在某个时刻 $原题公式$ ，两个人的位置相同，则称这两个人在时刻 $原题公式$ 相遇。特别地， $原题公式$ 时刻也算在内。现在你可以从 $原题公式$ 个人中选出若干人，使得在任意时刻都不存在两个人相遇。请输出最多能选出多少个人。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $原题公式$ 代表数据组数，每组测试数据描述如下：第一行输入一个整数 $原题公式$ ，表示队伍人数。第二行输入 $原题公式$ 个整数 $原题公式$ ，表示所有成员的初始位置。第三行输入 $原题公式$ 个整数 $原题公式$ ，表示所有成员的目标位置。此外，保证单个测试文件的 $原题公式$ 不超过 $原题公式$ 。

输出描述

对于每一组测试数据，新起一行，输出答案。

样例1

输入

输出

2
4

样例解释 第一组的三个人分别是 $原题公式$ 、 $原题公式$ 、 $原题公式$ 。前两个人一个向右、一个向左，会在 $原题公式$ 时同时到达位置 $原题公式$ ，因此不能同时选。第三个人始终停在 $原题公式$ ，与前两个人都不冲突，所以最多选出 $原题公式$ 个人。第二组的四个人的初始位置与目标位置相同，全都原地不动且位置两两不同， $原题公式$ 个人可以全部选出。

样例2

输入

输出

样例解释 前两个人在 $原题公式$ 时都站在位置 $原题公式$ ，已经算作相遇，最多只能保留其中一个。保留 $原题公式$ 与 $原题公式$ 这两个人，前者始终在后者左侧，答案是 $原题公式$ 。

题解：排序 + 严格最长上升子序列

题目问题拆解

每个人从 $原题公式$ 匀速走向 $原题公式$ ，到了就停下。要选出最多的人，使任意两人在任意时刻都不站在同一位置。这是一道判定条件比算法更难的题：难点在于把”两人永不相遇”这个含时间的性质，翻译成只跟 $原题公式$ 、 $原题公式$ 有关的静态条件。

算法实现

先把时间从相遇里剥出来。记位置差 $原题公式$ ，两条轨迹连续， $原题公式$ 也连续，且 $原题公式$ 两值异号时由介值定理 $原题公式$ 中途必取到 $原题公式$ ，两人一定相遇；某个值为 $原题公式$ 则起点重合（ $原题公式$ 就撞上）或终点重合，同样相遇。所以不相遇必须有 $原题公式$ 。它也是充分的，靠的是每个人只朝一个方向走。设 $原题公式$ 而两人在 $原题公式$ 点相遇， $原题公式$ 是从左边追上来的，追上那一刻 $原题公式$ 必在向右走， $原题公式$ 要么向左走要么已停住；轨迹单调，此后 $原题公式$ 不会回到 $原题公式$ 左侧、 $原题公式$ 不会回到 $原题公式$ 右侧，得 $原题公式$ ，与 $原题公式$ 矛盾。于是条件化成起点顺序与终点顺序一致。把人按 $原题公式$ 升序排队，被选中者的 $原题公式$ 必须严格递增，答案即 $原题公式$ 的严格最长上升子序列长度。 $原题公式$ 相同的两人在 $原题公式$ 已经相遇，排序时令这一组内部 $原题公式$ 降序，组内就凑不出上升对，至多选走一个，不必特判。朴素的 $原题公式$ 逐对转移在 $原题公式$ 下要做 $原题公式$ 次比较，必然超时。改用 $原题公式$ 数组，记的取值是某条长度为的严格上升链的结尾 $原题公式$ 它随 $原题公式$ 天然递增，每个 $原题公式$ 二分找第一个不小于它的位置替换，越界则接在末尾。二分取 bisect_left 而非 bisect_right，等值也被替换，保证的才是严格递增。

时空复杂度分析

时间复杂度 ： $原题公式$ 。瓶颈是排序，其后每人只做一次 $原题公式$ 的二分； $原题公式$ 为 $原题公式$ 时总量在千万级以内。 空间复杂度 ： $原题公式$ ，排序后的数对与 $原题公式$ 数组各一份。 Java

// 不相遇的最多人数 - 排序 + 严格最长上升子序列
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class Main {
    // 求最多能选出多少人两两永不相遇
    static int maxNonMeeting(int[][] people) {
        // 两人永不相遇要求起点不同、终点不同，且起点的先后顺序与终点的先后顺序一致，
        // 所以被选中的人按起点排好队后，终点也必须严格递增。
        // 起点升序、起点相同时终点降序，这样同一个起点上最多只会被选走一个人
        Arrays.sort(people, (a, b) -> {
            if (a[0] != b[0]) {
                return Integer.compare(a[0], b[0]);
            }
            return Integer.compare(b[1], a[1]);
        });
        // tails[k]: 长度为 k+1 的上升链，结尾终点能取到的最小值；len 是已用长度
        int[] tails = new int[people.length];
        int len = 0;
        for (int[] person : people) {
            int q = person[1];
            // 二分找第一个不小于 q 的位置：等值也要被替换掉，才能保证严格上升
            int lo = 0;
            int hi = len;
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (tails[mid] < q) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            // 落在末尾说明比所有链尾都大，链长加一；否则用更小的结尾替换，给后面留空间
            tails[lo] = q;
            if (lo == len) {
                len++;
            }
        }
        return len;
    }

    public static void main(String[] args) throws Exception {
        // 数据量大，用 StreamTokenizer 按空白切词读入，输出走带缓冲的 PrintWriter
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(System.out);
        in.nextToken();
        int t = (int) in.nval;
        // 多组测试：每组三行（人数、起点、终点），算完一组就直接输出这一组的答案
        while (t-- > 0) {
            in.nextToken();
            int n = (int) in.nval;
            int[][] people = new int[n][2];
            // 起点和终点分两行给出，先读完全部起点，再回填各人的终点
            for (int i = 0; i < n; i++) {
                in.nextToken();
                people[i][0] = (int) in.nval;
            }
            for (int i = 0; i < n; i++) {
                in.nextToken();
                people[i][1] = (int) in.nval;
            }
            out.println(maxNonMeeting(people));
        }
        out.flush();
    }
}

第二题：曼哈顿距离最大的两块空地

题目描述

你得到一张地图，它有 $原题公式$ 行， $原题公式$ 列。地图的每个格子是下面两种之一：空地用字符 . 表示，障碍物用字符 # 表示。 AK机和他的同伴想站在两块不同的空地上，让他们之间的曼哈顿距离尽量大。两点 $原题公式$ 与 $原题公式$ 的曼哈顿距离定义为 $原题公式$ 。请你输出任意一组满足曼哈顿距离最大的两块空地的位置。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $原题公式$ 代表数据组数，每组测试数据描述如下：第一行输入两个整数 $原题公式$ 表示地图的行数和列数。此后 $原题公式$ 行，每行输入一个长度为 $原题公式$ 的字符串，保证仅由字符 . 与 # 组成。保证每组测试数据中空地的数量至少为 $原题公式$ 。除此之外，保证单个测试文件的 $原题公式$ 不超过 $原题公式$ 。

输出描述

对于每一组测试数据，新起一行输出四个整数 $原题公式$ ，表示你找到的两块空地的坐标，其中 $原题公式$ 表示行， $原题公式$ 表示列，均从 $原题公式$ 开始编号。如果有多个解方案，你可以输出任意一个，系统会自动判定是否正确。

样例1

输入

2
2 3
..#
#..
1 4
.##.

输出

1 1 2 3
1 1 1 4

样例解释 第一组的空地是 $原题公式$ ，其中 $原题公式$ 与 $原题公式$ 的曼哈顿距离为 $原题公式$ ，是所有取法里最大的。第二组只有 $原题公式$ 与 $原题公式$ 两块空地，曼哈顿距离为 $原题公式$ ，只能选这一组。

样例2

输入

1
3 3
#.#
...
#.#

输出

1 2 3 2

样例解释 四块空地围成一个十字，最远的一对是上下两端 $原题公式$ 与 $原题公式$ ，距离为 $原题公式$ 。左右两端 $原题公式$ 与 $原题公式$ 距离同样是 $原题公式$ ，输出这一组也会被判定为正确。

题解：切比雪夫转化

题目问题拆解

在 $原题公式$ 行 $原题公式$ 列的地图上挑两块不同的空地，使两者的曼哈顿距离最大，输出任意一组。这是一道靠换坐标把二维问题拆成两个一维问题的题：两两枚举空地是 $原题公式$ ， $原题公式$ 达 $原题公式$ 时最坏要跑 $原题公式$ 次，必须先把那两个绝对值解开。

算法实现

难点在于 $原题公式$ 里两个绝对值互相牵制，谁也定不下来。记 $原题公式$ 、 $原题公式$ ，恒有 $原题公式$ ：两数同号时 $原题公式$ 取到 $原题公式$ 、 $原题公式$ 更小，异号时两者互换角色。而 $原题公式$ 与 $原题公式$ 各自只跟一个新坐标有关。令 $原题公式$ 就有 $原题公式$ 、 $原题公式$ ，于是两点的曼哈顿距离等于它们在 $原题公式$ 轴与 $原题公式$ 轴上距离的较大者。两个维度就此解耦，最大距离是 $原题公式$ 这个上界能取到。取 $原题公式$ 最大与 $原题公式$ 最小的那两块空地，它们的 $原题公式$ 差恰为 $原题公式$ ，故曼哈顿距离不小于该值；又不可能超过全局最大值，两头一夹即相等，直接输出这一对。 $原题公式$ 侧同理，哪侧极差大就输出哪侧。扫描还能再省一层。同一行里 $原题公式$ 随 $原题公式$ 递增、 $原题公式$ 随 $原题公式$ 递减，所以每行只有最左和最右两块空地够得着这四个极值，用 find 与 rfind 各定位一次即可，整行不必逐格判断。两点必然互异：题面保证每组至少有两块空地，若两个极差同时为 $原题公式$ ，则所有空地的 $原题公式$ 与 $原题公式$ 都相同，而 $原题公式$ 唯一确定 $原题公式$ ，等于说只有一块空地，与保证矛盾。

时空复杂度分析

时间复杂度 ： $原题公式$ 。瓶颈是读入整张地图，扫描阶段每行只做两次定位， $原题公式$ 为 $原题公式$ 时总量在百万级以内。 空间复杂度 ： $原题公式$ ，存下当前这组地图；极值本身只占常数个变量。 Java

// 曼哈顿距离最大的两块空地 - 切比雪夫转化
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
    // 求出一组曼哈顿距离最大的空地，返回 {r1, c1, r2, c2}，行列均从 1 开始
    static int[] solveGrid(int n, String[] rows) {
        // |r1-r2|+|c1-c2| 等于 |u1-u2| 与 |v1-v2| 中的较大者（u=r+c，v=r-c），
        // 所以最大距离就是 u 的极差与 v 的极差里更大的那个，只需记住四个极值点
        int maxU = Integer.MIN_VALUE, minU = Integer.MAX_VALUE;
        int maxV = Integer.MIN_VALUE, minV = Integer.MAX_VALUE;
        int[] pMaxU = null, pMinU = null, pMaxV = null, pMinV = null;
        for (int i = 0; i < n; i++) {
            int first = rows[i].indexOf('.');
            // 整行都是障碍物，对四个极值都没有贡献
            if (first < 0) {
                continue;
            }
            int last = rows[i].lastIndexOf('.');
            int r = i + 1;
            // 同一行里 u=r+c 随 c 递增、v=r-c 随 c 递减，
            // 所以本行只有最左和最右两块空地可能成为极值点，不必逐格扫
            int cl = first + 1;
            int cr = last + 1;
            if (r + cr > maxU) {
                maxU = r + cr;
                pMaxU = new int[]{r, cr};
            }
            if (r + cl < minU) {
                minU = r + cl;
                pMinU = new int[]{r, cl};
            }
            if (r - cl > maxV) {
                maxV = r - cl;
                pMaxV = new int[]{r, cl};
            }
            if (r - cr < minV) {
                minV = r - cr;
                pMinV = new int[]{r, cr};
            }
        }
        // 取极差更大的那一侧：这两点的真实曼哈顿距离恰好等于该极差，故必为最优
        boolean useU = maxU - minU >= maxV - minV;
        int[] a = useU ? pMinU : pMinV;
        int[] b = useU ? pMaxU : pMaxV;
        return new int[]{a[0], a[1], b[0], b[1]};
    }

    public static void main(String[] args) throws Exception {
        // 行长可达 2*10^5，用带缓冲的读入按整行取，避免逐字符的系统调用
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        int t = Integer.parseInt(br.readLine().trim());
        while (t-- > 0) {
            // 这一行是 n 和 m，列数 m 用不上：每行字符串自带长度
            String[] head = br.readLine().trim().split("\\s+");
            int n = Integer.parseInt(head[0]);
            String[] rows = new String[n];
            for (int i = 0; i < n; i++) {
                rows[i] = br.readLine().trim();
            }
            int[] res = solveGrid(n, rows);
            out.println(res[0] + " " + res[1] + " " + res[2] + " " + res[3]);
        }
        // T 可达 2*10^5，逐行裸输出会真 TLE，最后统一刷缓冲
        out.flush();
    }
}

这篇文章有帮助吗？

| GitHub 留言