【笔试题解】2024-08-24-美团秋招
大家好这里是程序员基德,今天给大家带来的是美团笔试题(改编题面)的题目解析。
感兴趣的朋友可以来订阅基德的笔试专栏,感谢大家的支持。
互联网刷题必备宝典🔗
第一题:移动瓶子
题目内容
小基初始位于 位置,二维平面上有 个瓶子,每个瓶子的位置为 。小基每次可以向上、下、左、右移动一格,每次移动的代价为 1。小基需要每次移动到一个瓶子的位置上,然后拿起瓶子把它放到 位置,每次最多只能拿一个瓶子。请问最少需要多少代价才能把所有瓶子都放到 位置上。
输入描述
第一行四个整数 ,表示小基初始位置和瓶子需要放置的位置。 接下来一行一个整数 ,表示瓶子的数量。 接下来 行,每行两个整数 ,表示第 个瓶子的位置。
输出描述
输出一个整数,表示最少需要多少代价。
样例1
输入:
0 0 1 1
2
1 0
2 2
输出:
6
说明: 先移动到 ,拿起瓶子,移动到 ,放下瓶子,代价为 2。 再移动到 ,拿起瓶子,移动到 ,放下瓶子,代价为 4。
题解
这道题的关键是理解除了第一次从 出发外,后面均是从 出发再回到 。因此需要枚举第一个拿取的瓶子,然后计算其他瓶子到 的路径总和。
时间复杂度: 空间复杂度:
三语言参考代码
- C++
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define N 100010
ll a, b, c, d;
ll site_x[N];
ll site_y[N];
int main(){
int n;
cin >> a >> b >> c >> d;
cin >> n;
ll res = 0;
for(int i = 0; i < n; i++){
cin >> site_x[i] >> site_y[i];
res = res + 2*(abs(site_x[i] - c) + abs(site_y[i] - d));
}
ll temp_res = res;
for(int i = 0; i < n; i++){
temp_res -= 2*(abs(site_x[i] - c) + abs(site_y[i] - d));
temp_res += (abs(site_x[i] - a) + abs(site_x[i] - c) + abs(site_y[i] - b) + abs(site_y[i] - d));
if(temp_res < res){
res = temp_res;
}
temp_res -= (abs(site_x[i] - a) + abs(site_x[i] - c) + abs(site_y[i] - b) + abs(site_y[i] - d));
temp_res += 2*(abs(site_x[i] - c) + abs(site_y[i] - d));
}
cout << res << endl;
return 0;
}
- Python
import sys
a, b, c, d = map(int, input().split())
n = int(input())
X = [0] * n
Y = [0] * n
ans = 0
idx = -1
mx = sys.maxsize
for i in range(n):
X[i], Y[i] = map(int, input().split())
x, y = X[i], Y[i]
t = abs(x - c) + abs(y - d)
dist = abs(x - a) + abs(y - b) - t
if idx == -1 or dist < mx:
idx = i
mx = dist
for i in range(n):
x, y = X[i], Y[i]
ans += 2 * (abs(x - c) + abs(y - d))
ans += mx
print(ans)
- Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long a = sc.nextLong();
long b = sc.nextLong();
long c = sc.nextLong();
long d = sc.nextLong();
int n = sc.nextInt();
long[][] bottles = new long[n][2];
long sum = 0;
for(int i = 0; i < n; i++){
bottles[i][0] = sc.nextInt();
sum += Math.abs(bottles[i][0] - c);
bottles[i][1] = sc.nextInt();
sum += Math.abs(bottles[i][1] - d);
}
sum *= 2;
long res = Long.MAX_VALUE;
long dis = 0;
for(int i = 0; i < n; i++){
dis = Math.abs(bottles[i][0] - a) + Math.abs(bottles[i][1] - b);
res = Math.min(res, sum - Math.abs(bottles[i][0] - c) - Math.abs(bottles[i][1] - d) + dis);
}
System.out.println(res);
}
}
第二题:数字操作
题目内容
小基有三个数字 ,她每次操作可以选择一个数字将其加一,最多可以操作 次。小基想知道 的最大值是多少?
由于这个数字可能很大,因此你需要输出答案对 取模后的结果。
输入描述
第一行四个正整数 表示数字和操作次数。
输出描述
输出一个整数表示答案。
样例1
输入:
1 2 3 1
输出:
12
说明: 对 1 操作一次,三个数字变成 [2,2,3],乘积为 12。
题解
这道题的关键是理解几何不等式:。要使乘积最大,三个数应该尽量相等。因此每次操作应该给最小的数加一。
时间复杂度: 空间复杂度:
三语言参考代码
- C++
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
long long arr[3];
cin >> arr[0] >> arr[1] >> arr[2];
long long k;
long long mod = 1e9+7;
cin >> k;
sort(arr, arr + 3);
long long needed = (arr[2] - arr[0]) + (arr[2] - arr[1]);
if (k >= needed) {
k -= needed;
arr[0] = arr[2];
arr[1] = arr[2];
arr[0] += k / 3;
arr[1] += k / 3;
arr[2] += k / 3;
long long remainder = k % 3;
if (remainder == 1) {
arr[2] += 1;
} else if (remainder == 2) {
arr[1] += 1;
arr[2] += 1;
}
} else {
if (k <= arr[1]-arr[0]){
arr[0] += k;
} else {
k -= arr[1]-arr[0];
arr[0] = arr[1];
arr[0] += k/2+k%2;
arr[1] += k/2;
}
}
long long result = ((arr[0] % mod) * (arr[1] % mod) % mod * (arr[2] % mod)) % mod;
cout << result << endl;
return 0;
}
- Python
a,b,c,k = list(map(int,input().split()))
mod = 10 ** 9 + 7
nums = [a,b,c]
nums.sort()
if 2 * nums[2] - nums[1] - nums[0] < k:
k -= 2 * nums[2] - nums[1] - nums[0]
temp = k // 3
num3 = nums[2] + temp
if k % 3 == 0:
res = num3 ** 3
elif k % 3 == 1:
res = num3 * num3 * (num3 + 1)
else:
res = num3 * (num3 + 1)**2
print(res % mod)
elif nums[1] - nums[0] < k <= 2 * nums[2] - nums[1] - nums[0]:
k -= nums[1] - nums[0]
temp = k // 2
num2 = nums[1] + temp
if k % 2 == 0:
res = num2 * num2 * nums[2]
elif k % 2 == 1:
num1 = num2 + 1
res = num1 * num2 * nums[2]
print(res % mod)
elif k <= nums[1] - nums[0]:
num1 = nums[0] + k
res = num1 * nums[1] * nums[2]
print(res % mod)
- Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
long[] nums = new long[3];
nums[0] = in.nextLong();
nums[1] = in.nextLong();
nums[2] = in.nextLong();
long k = in.nextLong();
int MOD = 1000000007;
Arrays.sort(nums);
long sub1 = nums[1] - nums[0];
long sub2 = nums[2] - nums[1];
double ans = 0;
if(k < sub1) {
nums[0] = (nums[0] + k) % MOD;
for(int i = 0; i < 3; i++) nums[i] %= MOD;
ans = nums[0] * nums[1] % MOD * nums[2] % MOD;
System.out.print((long)ans);
return;
}
nums[0] = (nums[0] + sub1) % MOD;
k -= sub1;
if(k/2 < sub2) {
nums[0] = (nums[0] + k/2 + (k%2==1?1:0)) % MOD;
nums[1] = (nums[1] + k/2) % MOD;
for(int i = 0; i < 3; i++) nums[i] %= MOD;
ans = nums[0] * nums[1] % MOD * nums[2] % MOD;
System.out.print((long)ans);
return;
}
nums[0] = (nums[0] + sub2) % MOD;
nums[1] = (nums[1] + sub2) % MOD;
k -= (sub2*2);
nums[0] = (nums[0] + k/3 + (k%3>=1?1:0)) % MOD;
nums[1] = (nums[1] + k/3 + (k%3>=2?1:0)) % MOD;
nums[2] = (nums[2] + k/3) % MOD;
ans = nums[0] * nums[1] % MOD * nums[2] % MOD;
System.out.print((long)ans);
}
}
第三题:商店购物
题目内容
小基的商店里只卖两种商品,"可乐"和"马克"。现在有 个人来到商店购物,第 个人有一个喜好区间 和购买目标商品,他只看货架上位于区间里的商品,并从中挑选 个保质期最长的可乐或者马克买走(如果有多个商品保质期相同,他会拿走区间中靠前的那个)。你能告诉小基每个人买走的商品编号吗?
输入描述
第一行输入两个整数 和 代表来商店购物的人数和商品数量。 第二行输入 个整数 代表商品的保质期。 第三行输入 个整数 代表商品的种类,其中, 代表"可乐"、 代表"马克"。 此后 行,第 行输入四个整数 和 代表第 个人的喜好区间、购买商品和购买件数。
输出描述
输出 行,第 行包含至多 个整数,代表第 个人购买的商品编号(如果有多个商品保质期相同,输出编号较小的那个),你需要按照从小到大的顺序依次输出;如果没有买到足够的商品,使用一个 替代。
样例1
输入:
5 5
2 3 4 5 6
1 1 0 1 1
1 3 1 2
1 3 1 2
1 3 0 5
1 5 1 1
1 5 0 1
输出:
2 1
-1
3 -1
5
-1
说明: 第一次询问,货架上的情况为 ( 代表非目标商品),先买第二件,再买第一件; 第二次询问,货架上的情况为 {x,x,,,}(x代表已售罄商品),此时无法购买,直接输出 ; 第三次询问,货架上的情况为 {} 由于只剩一件商品,故先购买第三件,后输出 代表没有买到足够数量的商品。
题解
这道题需要使用线段树来维护区间最大值。每次查询时,找到区间内目标商品中保质期最长的商品,然后将其删除(标记为已售出)。如果找不到足够数量的商品,则输出 -1。
时间复杂度: 空间复杂度:
三语言参考代码
- C++
#include <iostream>
#include <vector>
using namespace std;
const int MAX_SIZE = 100000;
const int LIMIT = MAX_SIZE + 10;
struct SegmentTree {
int size;
vector<int> tree;
vector<int> data;
void init(int len, vector<int>& d) {
size = len;
tree.assign(4 * size, 0);
data = d;
}
void build(int node, int start, int end) {
if (start == end) {
tree[node] = start;
} else {
int mid = (start + end) / 2;
build(2 * node, start, mid);
build(2 * node + 1, mid + 1, end);
tree[node] = compare(tree[2 * node], tree[2 * node + 1]);
}
}
int compare(int idx1, int idx2) {
if (data[idx1] > data[idx2] || (data[idx1] == data[idx2] && idx1 < idx2))
return idx1;
return idx2;
}
void update(int node, int start, int end, int idx, int value) {
if (start == end) {
data[idx] = value;
} else {
int mid = (start + end) / 2;
if (idx <= mid)
update(2 * node, start, mid, idx, value);
else
update(2 * node + 1, mid + 1, end, idx, value);
tree[node] = compare(tree[2 * node], tree[2 * node + 1]);
}
}
int query(int node, int start, int end, int l, int r) {
if (r < start || l > end)
return 0;
if (l <= start && end <= r)
return tree[node];
int mid = (start + end) / 2;
int left = query(2 * node, start, mid, l, r);
int right = query(2 * node + 1, mid + 1, end, l, r);
return compare(left, right);
}
void add(int idx, int value) {
update(1, 1, size, idx, value);
}
void remove(int idx) {
update(1, 1, size, idx, -1);
}
int getMaxIndex(int l, int r) {
return query(1, 1, size, l, r);
}
} segment[2];
int main() {
int numOps, numElems;
cin >> numOps >> numElems;
vector<int> arr[2];
arr[0].resize(numElems + 1, -1);
arr[1].resize(numElems + 1, -1);
vector<int> A(numElems), B(numElems);
for (int i = 0; i < numElems; ++i) {
cin >> A[i];
}
for (int i = 0; i < numElems; ++i) {
cin >> B[i];
arr[B[i]][i + 1] = A[i];
}
for (int i = 0; i < 2; ++i) {
segment[i].init(numElems, arr[i]);
segment[i].build(1, 1, numElems);
}
while (numOps--) {
int left, right, type, numQueries;
cin >> left >> right >> type >> numQueries;
while (numQueries--) {
int index = segment[type].getMaxIndex(left, right);
int value = segment[type].data[index];
segment[type].remove(index);
cout << (value != -1 ? index : -1) << ' ';
if (value == -1) break;
}
cout << '\n';
}
return 0;
}
- Python
class SegmentTree:
def __init__(self, n, data):
self.size = n
self.data = data
self.tree = [0] * (4 * n)
self.build(1, 1, n)
def build(self, node, start, end):
if start == end:
self.tree[node] = start
else:
mid = (start + end) // 2
self.build(2 * node, start, mid)
self.build(2 * node + 1, mid + 1, end)
self.tree[node] = self.compare(self.tree[2 * node], self.tree[2 * node + 1])
def compare(self, idx1, idx2):
if self.data[idx1] > self.data[idx2] or (self.data[idx1] == self.data[idx2] and idx1 < idx2):
return idx1
return idx2
def update(self, node, start, end, idx, value):
if start == end:
self.data[idx] = value
else:
mid = (start + end) // 2
if idx <= mid:
self.update(2 * node, start, mid, idx, value)
else:
self.update(2 * node + 1, mid + 1, end, idx, value)
self.tree[node] = self.compare(self.tree[2 * node], self.tree[2 * node + 1])
def query(self, node, start, end, l, r):
if r < start or l > end:
return 0
if l <= start and end <= r:
return self.tree[node]
mid = (start + end) // 2
left = self.query(2 * node, start, mid, l, r)
right = self.query(2 * node + 1, mid + 1, end, l, r)
return self.compare(left, right)
def remove(self, idx):
self.update(1, 1, self.size, idx, -1)
def get_max_index(self, l, r):
return self.query(1, 1, self.size, l, r)
def main():
n, m = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
arr = [[-1] * (m + 1) for _ in range(2)]
for i in range(m):
arr[B[i]][i + 1] = A[i]
segment = [SegmentTree(m, arr[i]) for i in range(2)]
for _ in range(n):
l, r, t, k = map(int, input().split())
result = []
for _ in range(k):
idx = segment[t].get_max_index(l, r)
val = segment[t].data[idx]
if val == -1:
result.append(-1)
break
result.append(idx)
segment[t].remove(idx)
if len(result) < k:
print(-1)
else:
print(*sorted(result))
if __name__ == "__main__":
main()
- Java
import java.util.*;
class SegmentTree {
int size;
int[] tree;
int[] data;
void init(int n, int[] d) {
size = n;
tree = new int[4 * size];
data = d;
build(1, 1, size);
}
void build(int node, int start, int end) {
if (start == end) {
tree[node] = start;
} else {
int mid = (start + end) / 2;
build(2 * node, start, mid);
build(2 * node + 1, mid + 1, end);
tree[node] = compare(tree[2 * node], tree[2 * node + 1]);
}
}
int compare(int idx1, int idx2) {
if (data[idx1] > data[idx2] || (data[idx1] == data[idx2] && idx1 < idx2))
return idx1;
return idx2;
}
void update(int node, int start, int end, int idx, int value) {
if (start == end) {
data[idx] = value;
} else {
int mid = (start + end) / 2;
if (idx <= mid)
update(2 * node, start, mid, idx, value);
else
update(2 * node + 1, mid + 1, end, idx, value);
tree[node] = compare(tree[2 * node], tree[2 * node + 1]);
}
}
int query(int node, int start, int end, int l, int r) {
if (r < start || l > end)
return 0;
if (l <= start && end <= r)
return tree[node];
int mid = (start + end) / 2;
int left = query(2 * node, start, mid, l, r);
int right = query(2 * node + 1, mid + 1, end, l, r);
return compare(left, right);
}
void remove(int idx) {
update(1, 1, size, idx, -1);
}
int getMaxIndex(int l, int r) {
return query(1, 1, size, l, r);
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] A = new int[m];
int[] B = new int[m];
for (int i = 0; i < m; i++) A[i] = sc.nextInt();
for (int i = 0; i < m; i++) B[i] = sc.nextInt();
int[][] arr = new int[2][m + 1];
for (int[] row : arr) Arrays.fill(row, -1);
for (int i = 0; i < m; i++) {
arr[B[i]][i + 1] = A[i];
}
SegmentTree[] segment = new SegmentTree[2];
for (int i = 0; i < 2; i++) {
segment[i] = new SegmentTree();
segment[i].init(m, arr[i]);
}
for (int i = 0; i < n; i++) {
int l = sc.nextInt();
int r = sc.nextInt();
int t = sc.nextInt();
int k = sc.nextInt();
List<Integer> result = new ArrayList<>();
for (int j = 0; j < k; j++) {
int idx = segment[t].getMaxIndex(l, r);
int val = segment[t].data[idx];
if (val == -1) {
result.clear();
result.add(-1);
break;
}
result.add(idx);
segment[t].remove(idx);
}
Collections.sort(result);
for (int num : result) {
System.out.print(num + " ");
}
System.out.println();
}
}
}
#刷题##美团##算法#互联网刷题笔试宝典,这里涵盖了市面上大部分的笔试题合集,希望助大家春秋招一臂之力