四季读书网
四季读书网

3月28日美团研发岗真题复盘

四季读书网 1 0
3月28日美团研发岗真题复盘
3月28日美团研发岗真题复盘 第1张

🔗刷题网址: bishipass.com

美团-2026.03.28-研发岗

01. LYA的折损压缩清单

问题描述

LYA 手里有一份长度为  的资源消耗清单，第  项的当前数值为 。

为了把月底报表压到更低，他手里有两类处理机会：

  • >
    压缩处理：选中一项后，把它改成 。
  • >
    抵扣处理：选中一项后，把它改成 。这个结果允许为负数。

每一项至多执行一次压缩处理，至多执行一次抵扣处理，两种处理都做也可以，顺序任选；当然也可以什么都不做。

整份清单中，压缩处理最多只能使用  次，抵扣处理最多只能使用  次。

请你计算，在最优安排下，整份清单所有数值之和最小能变成多少。

输入格式

每个测试文件包含多组测试数据。

第一行输入一个整数 ，表示测试数据组数。

对于每组测试数据：

  • >
    第一行输入四个整数 。
  • >
    第二行输入  个整数 。

输出格式

对于每组测试数据，输出一行一个整数，表示最小可能的总和。

样例输入

3
3 1 1 3
5 1 7
1 1 1 5
9
1 0 1 10
3

样例输出

6
-1
-7

数据范围

  • >
  • >
  • >
  • >
  • >
  • >
    单个测试文件内所有测试数据的  之和不超过 

题解

先把两种操作拆开看。

对某个数 ：

  • >
    压缩处理会把它变成 ，因此带来的收益是。
  • >
    抵扣处理的收益恒定就是 。

如果同一项两种都做，最佳顺序一定是先压缩再抵扣。因为这样最终值是，比先抵扣再压缩更小。

于是这题就变得很直接了：

  • >
    抵扣处理无论放在哪一项，收益都一样，都是 ，所以只要还有次数就一定值得用满，共减少 。
  • >
    压缩处理要挑收益最大的若干项，也就是挑出  最大的  个数。

所以答案就是：

前大的之和

把所有  算出来排序，取前  个即可。

时间复杂度是 ，空间复杂度是 。

参考代码

  • >
    Python
import sys

input = lambda: sys.stdin.readline().strip()


defsolve() -> None:
    t = int(input())
    out = []
for _ in range(t):
        n, limit_half, limit_sub, k = map(int, input().split())
        arr = list(map(int, input().split()))

        total = sum(arr)
        gains = [((x + 1) // 2) for x in arr]
        gains.sort(reverse=True)

        best_half = sum(gains[:limit_half])
        answer = total - best_half - limit_sub * k
        out.append(str(answer))

    print("\n".join(out))


if __name__ == "__main__":
    solve()
  • >
    Cpp
#include<bits/stdc++.h>
usingnamespacestd;

intmain(){
    ios::sync_with_stdio(false);
cin.tie(nullptr);

int T;
cin >> T;
while (T--) {
int n, limitHalf, limitSub;
longlong k;
cin >> n >> limitHalf >> limitSub >> k;

vector<longlong> gains;
        gains.reserve(n);
longlong total = 0;

for (int i = 0; i < n; ++i) {
longlong x;
cin >> x;
            total += x;
            gains.push_back((x + 1) / 2);
        }

        sort(gains.begin(), gains.end(), greater<longlong>());

longlong bestHalf = 0;
for (int i = 0; i < limitHalf; ++i) {
            bestHalf += gains[i];
        }

cout << total - bestHalf - 1LL * limitSub * k << '\n';
    }
return0;
}
  • >
    Java
import java.io.*;
import java.util.*;

publicclassMain{
privatestaticclassFastScanner{
privatefinal InputStream in = System.in;
privatefinalbyte[] buffer = newbyte[1 << 16];
privateint ptr = 0;
privateint len = 0;

privateintread()throws IOException {
if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
if (len <= 0) {
return -1;
                }
            }
return buffer[ptr++];
        }

longnextLong()throws IOException {
int c;
do {
                c = read();
            } while (c <= ' ' && c != -1);

long sign = 1;
if (c == '-') {
                sign = -1;
                c = read();
            }

long value = 0;
while (c > ' ') {
                value = value * 10 + c - '0';
                c = read();
            }
return value * sign;
        }
    }

publicstaticvoidmain(String[] args)throws Exception {
        FastScanner fs = new FastScanner();
        StringBuilder out = new StringBuilder();

int t = (int) fs.nextLong();
while (t-- > 0) {
int n = (int) fs.nextLong();
int limitHalf = (int) fs.nextLong();
int limitSub = (int) fs.nextLong();
long k = fs.nextLong();

long total = 0;
long[] gains = newlong[n];
for (int i = 0; i < n; ++i) {
long x = fs.nextLong();
                total += x;
                gains[i] = (x + 1) / 2;
            }

            Arrays.sort(gains);
long bestHalf = 0;
for (int i = 0; i < limitHalf; ++i) {
                bestHalf += gains[n - 1 - i];
            }

long answer = total - bestHalf - (long) limitSub * k;
            out.append(answer).append('\n');
        }

        System.out.print(out);
    }
}

02. K小姐的交错收益序列

问题描述

K小姐手里有一个长度为  的整数序列 。

她准备从中挑出一个子序列 ，要求保持原有相对顺序，但不要求连续。

这份子序列的收益定义为：

也就是说，第奇数个被选中的数会加到答案里，第偶数个会减掉。

请你求出  的最大可能值。

子序列允许为空；如果你不选任何数，那么收益视为 。

输入格式

每个测试文件包含多组测试数据。

第一行输入一个整数 ，表示测试数据组数。

对于每组测试数据：

  • >
    第一行输入一个整数 。
  • >
    第二行输入  个整数 。

输出格式

对于每组测试数据，输出一行一个整数，表示最大可能收益。

样例输入

3
4
4 2 5 3
3
-5 -2 -7
5
1 5 2 3 4

样例输出

7
5
7

样例说明

第一组数据可以选择子序列 ，得到 。

数据范围

  • >
  • >
  • >
  • >
    所有测试数据中的  之和不超过 

题解

这题用两个状态就够了。

扫描到当前位置时，维护：

  • >
    odd：已经选出的子序列长度为奇数时，能够得到的最大收益。
  • >
    even：已经选出的子序列长度为偶数时，能够得到的最大收益。

初始时：

  • >
    空子序列长度为偶数，所以 even = 0。
  • >
    还没有办法凑出奇数长度子序列，所以 odd = -inf。

现在处理一个新数 ，有两种选择：

  • >
    不选它，状态保持不变。
  • >
    选它。

如果当前去更新奇数长度，那么它一定是接在一个偶数长度子序列后面，于是：

如果当前去更新偶数长度，那么它一定是接在一个奇数长度子序列后面，于是：

每个数只用一次，所以转移时要先保存旧状态。

最后答案就是 。其中 even 至少是空子序列的 ，因此全负数组也能自然得到答案 。

时间复杂度是 ，空间复杂度是 。

参考代码

  • >
    Python
import sys

input = lambda: sys.stdin.readline().strip()


defsolve() -> None:
    t = int(input())
    out = []
    neg_inf = -(10 ** 30)

for _ in range(t):
        n = int(input())
        arr = list(map(int, input().split()))

        odd = neg_inf
        even = 0

for x in arr:
            new_odd = max(odd, even + x)
            new_even = max(even, odd - x)
            odd, even = new_odd, new_even

        out.append(str(max(odd, even)))

    print("\n".join(out))


if __name__ == "__main__":
    solve()
  • >
    Cpp
#include<bits/stdc++.h>
usingnamespacestd;

intmain(){
    ios::sync_with_stdio(false);
cin.tie(nullptr);

int T;
cin >> T;
while (T--) {
int n;
cin >> n;

longlong odd = -(1LL << 60);
longlong even = 0;

for (int i = 0; i < n; ++i) {
longlong x;
cin >> x;

longlong newOdd = max(odd, even + x);
longlong newEven = max(even, odd - x);
            odd = newOdd;
            even = newEven;
        }

cout << max(odd, even) << '\n';
    }
return0;
}
  • >
    Java
import java.io.*;

publicclassMain{
privatestaticclassFastScanner{
privatefinal InputStream in = System.in;
privatefinalbyte[] buffer = newbyte[1 << 16];
privateint ptr = 0;
privateint len = 0;

privateintread()throws IOException {
if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
if (len <= 0) {
return -1;
                }
            }
return buffer[ptr++];
        }

longnextLong()throws IOException {
int c;
do {
                c = read();
            } while (c <= ' ' && c != -1);

long sign = 1;
if (c == '-') {
                sign = -1;
                c = read();
            }

long value = 0;
while (c > ' ') {
                value = value * 10 + c - '0';
                c = read();
            }
return value * sign;
        }
    }

publicstaticvoidmain(String[] args)throws Exception {
        FastScanner fs = new FastScanner();
        StringBuilder out = new StringBuilder();

int t = (int) fs.nextLong();
while (t-- > 0) {
int n = (int) fs.nextLong();
long odd = -(1L << 60);
long even = 0;

for (int i = 0; i < n; ++i) {
long x = fs.nextLong();
long newOdd = Math.max(odd, even + x);
long newEven = Math.max(even, odd - x);
                odd = newOdd;
                even = newEven;
            }

            out.append(Math.max(odd, even)).append('\n');
        }

        System.out.print(out);
    }
}

03. A先生的双端观测区间

问题描述

A先生沿着一条巡检通道摆放了  个观测点，第  个观测点的高度为 。

他想统计有多少个长度大于  的连续区间  满足：

也就是说，一个区间能被记入答案，当且仅当它的左右端点高度之和，严格大于这个区间里的最高观测点高度。

请你输出满足条件的区间数量。

输入格式

  • >
    第一行输入一个整数 ，表示观测点个数。
  • >
    第二行输入  个整数 。

输出格式

输出一个整数，表示满足条件的区间数量。

样例输入

3
1 2 3

样例输出

3

数据范围

  • >
  • >

题解

把一个区间的最高点拎出来看，这题就有结构了。

#1. 用笛卡尔树给每个区间分配唯一的“最高点”

我们建立一棵最大笛卡尔树：

  • >
    中序遍历顺序就是原数组下标顺序。
  • >
    父节点的高度不小于子节点高度。
  • >
    如果有多个相同最大值，固定把区间内最靠左的那个最大值当作代表。

这样一来，每个区间都能唯一对应到一个节点 ：

  • >
     是这个区间里的最高点代表；
  • >
    区间左端点在  的左子树或就是  自己；
  • >
    区间右端点在  的右子树或就是  自己。

#2. 经过某个节点  的区间怎么数

设  的高度是 。

所有由  负责统计的区间分成两类：

  • >
    一端点就是  本身。
  • >
    左端点在左子树，右端点在右子树。

第一类很好算。

因为所有高度都是正数，只要区间长度大于 ，若一端点是 ，另一端点高度设为 ，那么：

一定成立。

所以这部分贡献就是：

左子树大小右子树大小

第二类需要统计：

  • >
    从左子树选一个值 ；
  • >
    从右子树选一个值 ；
  • >
    满足 。

#3. 小边枚举，大边二分

如果我们能拿到左右子树中所有高度的有序表，那么就可以：

  • >
    枚举较短那一边的每个值 ；
  • >
    在较长那一边里二分出第一个大于  的位置；
  • >
    后面的数都能和它配对成功。

这样统计完当前节点后，再把左右子树的有序表和  自己合并成一张新的有序表，交给父节点继续使用。

#4. 复杂度

每个节点都会把两个子树的有序表合并一次。

在统计跨两侧配对时，总是枚举更短的那一边，因此每个元素被当作“小边元素”参与二分的次数是  级别。

总时间复杂度是 ，空间复杂度是 。

参考代码

  • >
    Python
import sys
from bisect import bisect_right

input = lambda: sys.stdin.readline().strip()


defsolve() -> None:
    n = int(input())
    arr = list(map(int, input().split()))

    left = [-1] * n
    right = [-1] * n
    stack = []

for i, value in enumerate(arr):
        last = -1
while stack and arr[stack[-1]] < value:
            last = stack.pop()
if stack:
            right[stack[-1]] = i
        left[i] = last
        stack.append(i)

    root = stack[0]

    order = []
    stack2 = [root]
while stack2:
        u = stack2.pop()
        order.append(u)
if left[u] != -1:
            stack2.append(left[u])
if right[u] != -1:
            stack2.append(right[u])

    store = [None] * n
    answer = 0

for u in reversed(order):
        left_values = [] if left[u] == -1else store[left[u]]
        right_values = [] if right[u] == -1else store[right[u]]

        answer += len(left_values) + len(right_values)

if len(left_values) > len(right_values):
            left_values, right_values = right_values, left_values

        limit = arr[u]
for x in left_values:
            answer += len(right_values) - bisect_right(right_values, limit - x)

        merged = []
        i = 0
        j = 0
        inserted = False

while i < len(left_values) or j < len(right_values):
if j == len(right_values) or (i < len(left_values) and left_values[i] <= right_values[j]):
                nxt = left_values[i]
                i += 1
else:
                nxt = right_values[j]
                j += 1

ifnot inserted and limit <= nxt:
                merged.append(limit)
                inserted = True
            merged.append(nxt)

ifnot inserted:
            merged.append(limit)

        store[u] = merged
if left[u] != -1:
            store[left[u]] = None
if right[u] != -1:
            store[right[u]] = None

    print(answer)


if __name__ == "__main__":
    solve()
  • >
    Cpp
#include<bits/stdc++.h>
usingnamespacestd;

intmain(){
    ios::sync_with_stdio(false);
cin.tie(nullptr);

int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
    }

vector<int> left(n, -1), right(n, -1), st;
    st.reserve(n);
for (int i = 0; i < n; ++i) {
int last = -1;
while (!st.empty() && a[st.back()] < a[i]) {
            last = st.back();
            st.pop_back();
        }
if (!st.empty()) {
            right[st.back()] = i;
        }
        left[i] = last;
        st.push_back(i);
    }

int root = st.front();
vector<int> order;
    order.reserve(n);
vector<int> stack2 = {root};
while (!stack2.empty()) {
int u = stack2.back();
        stack2.pop_back();
        order.push_back(u);
if (left[u] != -1) {
            stack2.push_back(left[u]);
        }
if (right[u] != -1) {
            stack2.push_back(right[u]);
        }
    }

vector<vector<int>> store(n);
longlong answer = 0;

for (int idx = n - 1; idx >= 0; --idx) {
int u = order[idx];
vector<int> leftValues = (left[u] == -1 ? vector<int>() : move(store[left[u]]));
vector<int> rightValues = (right[u] == -1 ? vector<int>() : move(store[right[u]]));

        answer += (longlong)leftValues.size() + (longlong)rightValues.size();

if (leftValues.size() > rightValues.size()) {
            swap(leftValues, rightValues);
        }

for (int x : leftValues) {
auto it = upper_bound(rightValues.begin(), rightValues.end(), a[u] - x);
            answer += rightValues.end() - it;
        }

vector<int> merged;
        merged.reserve(leftValues.size() + rightValues.size() + 1);
int i = 0;
int j = 0;
bool inserted = false;
while (i < (int)leftValues.size() || j < (int)rightValues.size()) {
int nxt;
if (j == (int)rightValues.size() || (i < (int)leftValues.size() && leftValues[i] <= rightValues[j])) {
                nxt = leftValues[i++];
            } else {
                nxt = rightValues[j++];
            }
if (!inserted && a[u] <= nxt) {
                merged.push_back(a[u]);
                inserted = true;
            }
            merged.push_back(nxt);
        }
if (!inserted) {
            merged.push_back(a[u]);
        }

        store[u] = move(merged);
    }

cout << answer << '\n';
return0;
}
  • >
    Java
import java.io.*;
import java.util.*;

publicclassMain{
privatestaticclassFastScanner{
privatefinal InputStream in = System.in;
privatefinalbyte[] buffer = newbyte[1 << 16];
privateint ptr = 0;
privateint len = 0;

privateintread()throws IOException {
if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
if (len <= 0) {
return -1;
                }
            }
return buffer[ptr++];
        }

intnextInt()throws IOException {
int c;
do {
                c = read();
            } while (c <= ' ' && c != -1);

int sign = 1;
if (c == '-') {
                sign = -1;
                c = read();
            }

int value = 0;
while (c > ' ') {
                value = value * 10 + c - '0';
                c = read();
            }
return value * sign;
        }
    }

privatestaticintupperBound(int[] arr, int target){
int left = 0;
int right = arr.length;
while (left < right) {
int mid = (left + right) >>> 1;
if (arr[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
return left;
    }

publicstaticvoidmain(String[] args)throws Exception {
        FastScanner fs = new FastScanner();
int n = fs.nextInt();
int[] a = newint[n];
for (int i = 0; i < n; ++i) {
            a[i] = fs.nextInt();
        }

int[] left = newint[n];
int[] right = newint[n];
        Arrays.fill(left, -1);
        Arrays.fill(right, -1);

int[] stack = newint[n];
int top = 0;
for (int i = 0; i < n; ++i) {
int last = -1;
while (top > 0 && a[stack[top - 1]] < a[i]) {
                last = stack[--top];
            }
if (top > 0) {
                right[stack[top - 1]] = i;
            }
            left[i] = last;
            stack[top++] = i;
        }

int root = stack[0];
int[] order = newint[n];
int orderSize = 0;
int[] stack2 = newint[n];
int top2 = 0;
        stack2[top2++] = root;
while (top2 > 0) {
int u = stack2[--top2];
            order[orderSize++] = u;
if (left[u] != -1) {
                stack2[top2++] = left[u];
            }
if (right[u] != -1) {
                stack2[top2++] = right[u];
            }
        }

int[][] store = newint[n][];
long answer = 0;

for (int idx = n - 1; idx >= 0; --idx) {
int u = order[idx];
int[] leftValues = (left[u] == -1 ? newint[0] : store[left[u]]);
int[] rightValues = (right[u] == -1 ? newint[0] : store[right[u]]);

            answer += leftValues.length + rightValues.length;

if (leftValues.length > rightValues.length) {
int[] tmp = leftValues;
                leftValues = rightValues;
                rightValues = tmp;
            }

for (int x : leftValues) {
int pos = upperBound(rightValues, a[u] - x);
                answer += rightValues.length - pos;
            }

int[] merged = newint[leftValues.length + rightValues.length + 1];
int i = 0;
int j = 0;
int t = 0;
boolean inserted = false;

while (i < leftValues.length || j < rightValues.length) {
int nxt;
if (j == rightValues.length || (i < leftValues.length && leftValues[i] <= rightValues[j])) {
                    nxt = leftValues[i++];
                } else {
                    nxt = rightValues[j++];
                }

if (!inserted && a[u] <= nxt) {
                    merged[t++] = a[u];
                    inserted = true;
                }
                merged[t++] = nxt;
            }
if (!inserted) {
                merged[t++] = a[u];
            }

            store[u] = merged;
if (left[u] != -1) {
                store[left[u]] = null;
            }
if (right[u] != -1) {
                store[right[u]] = null;
            }
        }

        System.out.print(answer);
    }
}

✨ 写在最后：

网站最近上线了八股和选额的功能啦。

最近卡片刷题已经全员开放了，八股和选择题都能直接刷。 我自己还挺喜欢这种刷法的，先看题、自己想，再翻面看答案，会比一直往下看题库更有“在准备面试”的感觉一点。 如果你最近也在刷八股，准备面试、可以来bishipass试试看哦。

3月28日美团研发岗真题复盘 第2张
3月28日美团研发岗真题复盘 第3张
3月28日美团研发岗真题复盘 第4张
3月28日美团研发岗真题复盘 第5张

文章来源： 四季读书网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至23467321@qq.com举报，一经查实，本站将立刻删除;如已特别标注为本站原创文章的，转载时请以链接形式注明文章出处，谢谢！

上一个深耕课堂促提升 精准把脉备中考

下一个当前已是最新一个了

相关文章

抱歉，评论功能暂时关闭!