美团8.13后端方向笔试

1. 魔法外卖。100% AC。

思路：贪心，尽量让每个订单的送达时间接近截止时间。

# 贪心，尽量让送达时间接近截止时间
def solution(n, t, dead_times:list):
    dead_times.sort()
    time_cost = t# 总配送时间
    times_delivery = 0# 配送的次数
    i = 0
    while i <= n - 2:
        # 找截止时间最接近的
        while i + 1 <= n - 1 and time_cost >= dead_times[i] \
                and time_cost >= dead_times[i + 1]:
            i += 1
        time_cost += t
        times_delivery += 1# 配送
        i += 1

    return n - times_delivery


if __name__ == '__main__':
    n, t = input().split()
    n, t = int(n), int(t)
    dead_times = input().split()
    dead_times = [int(x) for x in dead_times]

    print(solution(n, t, dead_times))

2. 扫地机器人。100% AC。

思路：简单模拟即可。

from collections import Counter

import numpy as np

# 简单模拟即可
def solution(n, m, k, orders:str):

    is_cleaned = np.zeros((n, m), dtype=int)# 地块是否被打扫
    is_cleaned[0][0] = 1
    i, j = 0, 0# 记录机器人当前的位置
    for o in range(len(orders)):
        if orders[o] == 'W':
            i, j = i - 1, j
            is_cleaned[i][j] = 1
        if orders[o] == 'A':
            i, j = i, j - 1
            is_cleaned[i][j] = 1
        if orders[o] == 'S':
            i, j = i + 1, j
            is_cleaned[i][j] = 1
        if orders[o] == 'D':
            i, j = i, j + 1
            is_cleaned[i][j] = 1
        # 全部地块已打扫完
        if 0 not in is_cleaned:
            return 'Yes', (o + 1)

    is_cleaned = is_cleaned.reshape(n * m)
    is_cleaned = is_cleaned.tolist()

    return 'No', Counter(is_cleaned)[0]


if __name__ == '__main__':
    n, m, k = input().split()
    n, m, k = int(n), int(m), int(k)
    orders = input()

    ans = solution(n, m, k, orders)
    print(ans[0])
    print(ans[1])

3. 合法元组数。64% AC。

思路：暴力。但是超时了。

def solution(n, a):

    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if a[i] - a[j] == 2 * a[j] - a[k]:
                    count += 1

    return count


if __name__ == '__main__':

    n = int(input())
    a = input().split()
    a = [int(x) for x in a]

    print(solution(n, a))

4. 扑克。18% AC。

思路：没时间了，就骗了点测试用例。

5. 生活在树上。100% AC。

思路：直接在数组上模拟二叉树。递归+回溯。

# 递归解决
def solution(n, money, sum, list_sum, index):

    list_sum.append(sum + money[index])

    index_left = 2 * index
    index_right = 2 * index + 1
    # 递归访问左右子树 用了隐藏回溯
    if index_left <= n:
        solution(n, money, sum + money[index], list_sum, index_left)
    if index_right <= n:
        solution(n, money, sum + money[index], list_sum, index_right)

    return


if __name__ == '__main__':

    n = int(input())
    money = input().split()
    money = [int(x) for x in money]
    money = [0] + money

    list_sum = []
    solution(n, money, 0, list_sum, 1)
    print(max(list_sum))

#美团笔试#