snowy

Appearance

On this page

美团前端笔试 ​

2023.3.25 ​

1.火车进站与出站。相当于栈的结构：例如可能1号火车驶入了火车站中的休息区s，在驶出之前2号火车驶入了。那么在这种情况下，1号火车需要等待2号火车倒车出去后才能出去（显然被后面驶入的2号火车挡住了，这个休息区s只有一个出入口）。
给定火车驶入休息区s的顺序、火车驶出休息区s的顺序，判断是否合理？

python
def validate_stack_sequences(pushed, popped):
    st = []
    n = len(pushed)
    j = 0
    for i in range(n):
        st.append(pushed[i])
        while st and st[-1] == popped[j]:
            st.pop()
            j += 1
    return not st

def main():
    T = int(input())
    ans = []

    for _ in range(T):
        m = int(input())
        pushed = list(map(int, input().split()))
        popped = list(map(int, input().split()))

        res = validate_stack_sequences(pushed, popped)
        ans.append(res)

    for x in ans:
        if x:
            print("Yes")
        else:
            print("No")

if __name__ == "__main__":
    main()

2.小美明天要去春游了。她非常喜欢吃巧克力，希望带尽可能多的巧克力在春游的路上吃。她现在有n个巧克力,很巧的是她所有的巧克力都是厚度一样的正方形的巧克力板。这n个巧克力板的边长分别是a1, a2, ... , an。因为都是厚度一致的正方形巧克力扳，我们认为第i个巧克力的重量为ai^2。小美现在准备挑选一个合适大小的包来装尽可能多的巧克力板，她十分需要你的帮助来在明天之前准备完成，请你帮帮她。
输入描述
第一行两个整数n和m,表示小美的巧克力数量和小美的询问数量。
第二行n个整数a1,a2, ..., an，表示n块正方形巧克力板的边长。注意你不能将巧克力板进行拆分。
第三行m个整数q1,q2,...,qm，第i个整数表示询问：如果小美选择一个能装qi重量的包，最多能装多少块巧克力板？
1 <= n,m <= 50000, 1 <= ai <= 10000, 1 <= qi <= 10^18
输出描述
输出一行m个整数，分别表示每次询问的答案。

样例输入
5 5
1 2 2 4 5
1 3 7 9 15
样例输出
1 1 2 3 3
以下是常规写法，用例只能通过18%。

python
def get_chocolate_cnt(length, bag_weight):
    dp = [0] * (bag_weight + 1)

    for i in range(len(length)):
        for j in range(bag_weight, length[i] * length[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - length[i] * length[i]] + 1)
    return dp[bag_weight]

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    q = list(map(int, input().split()))

    ans = []
    for i in range(len(q)):
        res = get_chocolate_cnt(a, q[i])
        ans.append(res)

    print(" ".join(map(str, ans)))

if __name__ == "__main__":
    main()

优化后的写法：前缀和+二分。

python
def main():
    n, m = map(int, input().split())
    cho = list(map(int, input().split()))
    cho = [x**2 for x in cho]
    aq = [0] * len(cho)
    for i in range(1, len(cho)):
      aq[i] = aq[i-1] + cho[i]
      
    bags = list(map(int, input().split()))
    for bag in bags:
      l, r = -1, len(cho)
      while l + 1 != r:
        m = (l + r) // 2
        if cho[m] > bag:
          r = m
        else:
          l = m
      print(r)
    
if __name__ == "__main__":
    main()