关注我们，每天更新大厂最新笔试题解析
前言
文末给大家推荐一下我们的活动，针对校招笔面试全覆盖的全程真一对一的提高，参加活动前会给你安排一个全面的摸底，摸底后会针对你的情况进行分析和对于参加活动的介绍，然后你再决定是否参加!
在线做题链接：https://niumacode.com/
滴滴的薪酬高，今年的hc数量也不少，是非常值得尝试的投递标的，对于27届的同学来讲，滴滴的暑期实习转正率也是第一梯队的。
本次笔试难度中等偏上，主要考察大规模数据的处理技巧以及多重约束条件下的最优化求解。
第一题（方格世界）：难度中等。 涉及差分数组与扫描线算法。核心是将大范围的“区间加法”转化为坐标点上的“单点增减”，完美规避了海量数据遍历导致的超时与内存溢出。
第二题（零件加工）：难度较高。 涉及二分答案与贪心区间维护。核心是将求“最小磨损量”转化为寻找“最大合法拼接高度”，并通过贪心策略动态收缩相邻位置的高度区间来验证答案。
方格世界
在线做题链接：https://niumacode.com/
题目描述：
方格世界中所有方格的长宽高均为 米。方格世界中有 个方格堆，编号依次为 。每个方格堆中的方格都是按照从下到上的方式堆成一列（假设有 个方格，则这 个方格堆成了一个长宽均为 米，高为 米的长方体）。初始时每个方格堆中的方格数量均为 。方格世界会下 场“方格雨”，第 场“方格雨”会使得编号在 到 之间的方格堆的方格数量增加 。 定义 表示经过“方格雨”后方格世界中高度大于等于 米的方格堆个数。你需要计算 中一共有多少不同的取值。
输入描述
输入第一行有两个整数 （）和 （），分别表示方格世界中方格堆的个数、“方格雨”的次数。 接下来 行中，第 行有三个整数 , （）和 （），分别表示“方格雨”作用的方格堆范围和增加的方格数量。
输出描述
输出一个整数，表示 中一共有多少不同的取值。
样例输入
10 4
7 8 5
5 7 5
1 2 1
3 5 3
样例输出
6
提示
第一场“方格雨”后各个方格堆中方格数量: [0 0 0 0 0 0 5 5 0 0]; 第二场“方格雨”后各个方格堆中方格数量: [0 0 0 0 5 5 10 5 0 0]; 第三场“方格雨”后各个方格堆中方格数量: [1 1 0 0 5 5 10 5 0 0]; 第四场“方格雨”后各个方格堆中方格数量: [1 1 3 3 8 5 10 5 0 0]. 依次计算 , , , , , , , , , , . 中一共有 个不同的取值。
思路与代码
由于 的值仅在 超过某个方格堆的高度时才发生变化，题目本质是求所有方格堆中出现了多少种不同的高度值；随着 变大， 会不断减小。只有当 恰好超过某一个方格堆的实际高度时， 的值才会发生变化。因此 的不同取值个数 = 方格世界中出现的不同高度（大于0的高度）的种类数 + 1（高度为0的情况）。我们利用差分思想将“方格雨”转化为坐标轴上的高度增减事件，按位置排序后通过扫描线累加得出各区间的高度，并用 Set 统计所有出现的不同正高度种类数，最后加 1（即高度为 0 的情况）即为答案。
import java.util.*;
publicclassMain{
publicstaticvoidmain(String[] args){
Scanner scan = new Scanner(System.in);
if (!scan.hasNextInt()) {
return;
}
int limit = scan.nextInt();
int opCount = scan.nextInt();
Item[] items = new Item[opCount * 2];
int index = 0;
for (int j = 0; j < opCount; j++) {
int start = scan.nextInt();
int end = scan.nextInt();
long diff = scan.nextLong();
items[index++] = new Item(start, diff);
items[index++] = new Item(end + 1, -diff);
}
Arrays.sort(items);
long currentVal = 0;
int lastPos = -1;
Set<Long> resSet = new HashSet<>();
for (int j = 0; j < items.length; j++) {
Item it = items[j];
if (lastPos != -1 && it.loc > lastPos) {
if (currentVal > 0) {
resSet.add(currentVal);
}
}
currentVal += it.delta;
lastPos = it.loc;
}
System.out.println(resSet.size() + 1);
}
staticclassItemimplementsComparable<Item> {
int loc;
long delta;
publicItem(int loc, long delta){
this.loc = loc;
this.delta = delta;
}
@Override
publicintcompareTo(Item target){
return Integer.compare(this.loc, target.loc);
}
}
}
零件加工
在线做题链接：https://niumacode.com/
题目描述：
小 Q 需要加工两个精密零件。这两个零件分别有 个关键位置，分别从 到 进行编号。在加工结束后，这两个零件最后会组合在一起，并且关键位置一一对应。现在，小 Q 拿到了经过粗加工后的零件。其中，第一个零件的第 个位置的高度为 ，第二个零件的第 个位置的高度为 。 小 Q 现在需要对两个零件进行精细加工。加工结束后，两个零件的所有关键位置在拼接后的高度必须相同。并且为了保证零件强度，精细加工后同一个零件编号相邻的两个位置的高度之差小于等于 。 你能否帮助小 Q 计算，要使精细加工后的零件满足上述要求，最少需要磨掉多少高度的零件？ 形式化的，给定两个数组 和 ，你需要找到两个数组 与 ，满足以下条件：
输入描述
第一行有一个整数 （），代表数据组数。 之后的每一组数据，第一行有两个整数 和 （，），含义如题面所述。 接下来 行，第 行有两个整数 和 （，），含义如题面所述。 保证所有 组输入数据的 之和小于等于 。
输出描述
共 行，每行一个整数，代表该组数据的答案。
样例输入
1
4 3
3 6
5 2
4 7
8 9
样例输出
16
思路与代码
该问题的核心是通过二分搜索找到最大可行的拼接高度 。由于 且零件只能磨短，每个位置的 都有一个基于当前 的合法取值区间；在验证某个 是否可行时，利用贪心思想维护区间交集，即从第一个位置开始，根据相邻位置差值不超过 的约束，不断推导并收缩后续位置的合法范围，若全过程区间始终有效（左端点 右端点），则该 可行，最终用总原始高度减去 即为最小磨损量。
import java.util.Scanner;
publicclassMain{
publicstaticvoidmain(String[] args){
Scanner reader = new Scanner(System.in);
if (!reader.hasNextInt()) return;
int numCases = reader.nextInt();
while (numCases-- > 0) {
int size = reader.nextInt();
long maxDiff = reader.nextLong();
long[] firstPart = newlong[size];
long[] secondPart = newlong[size];
long minCeiling = Long.MAX_VALUE;
long totalMaterial = 0;
for (int idx = 0; idx < size; idx++) {
firstPart[idx] = reader.nextLong();
secondPart[idx] = reader.nextLong();
minCeiling = Math.min(minCeiling, firstPart[idx] + secondPart[idx]);
totalMaterial += firstPart[idx] + secondPart[idx];
}
long lft = 0;
long rgt = minCeiling;
long optimalTarget = 0;
while (lft <= rgt) {
long m = lft + (rgt - lft) / 2;
if (verify(m, firstPart, secondPart, size, maxDiff)) {
optimalTarget = m;
lft = m + 1;
} else {
rgt = m - 1;
}
}
System.out.println(totalMaterial - (long) size * optimalTarget);
}
reader.close();
}
privatestaticbooleanverify(long targetH, long[] fPart, long[] sPart, int len, long limit){
long minValid = Math.max(0, targetH - sPart[0]);
long maxValid = Math.min(fPart[0], targetH);
if (minValid > maxValid) returnfalse;
for (int j = 1; j < len; j++) {
long currMin = Math.max(0, targetH - sPart[j]);
long currMax = Math.min(fPart[j], targetH);
minValid = Math.max(currMin, minValid - limit);
maxValid = Math.min(currMax, maxValid + limit);
if (minValid > maxValid) returnfalse;
}
returntrue;
}
}
