【笔试题解】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();
        }
    }
}
#刷题##美团##算法#
互联网刷题笔试宝典 文章被收录于专栏

互联网刷题笔试宝典,这里涵盖了市面上大部分的笔试题合集,希望助大家春秋招一臂之力

全部评论

相关推荐

评论
1
1
分享

创作者周榜

更多
牛客网
牛客企业服务