蹲一下团子8.10的笔试

#秋招笔试#

第三题都没写,死磕第二题,但是还是超时,只过了35%。求大佬指点迷津,也不知道团子进面的笔试分要求多少,是不是第二题没全过就等于寄了

1. 第一题比较简单,输入的时候存一下密码长度就行

2. 第二题超时,抛砖引玉一下,求大佬指点

import sys

def get_mex(elements):
    mex = 0
    tempele = set(elements)
    while mex in tempele:
        mex += 1
    return mex

def calc_min(elements, k, x):
    cost = min(x, k*get_mex(elements[-1:]))
    for i in reversed(range(len(elements)-1)):
        cost = min(k*get_mex(elements[i:]), x+cost)
    return cost

T = int(sys.stdin.readline().strip())
for _ in range(T):
    temp = sys.stdin.readline().strip().split()
    n,k,x = int(temp[0]), int(temp[1]), int(temp[2])
    temp = sys.stdin.readline().strip().split()
    elements = [int(i) for i in temp]
    result = calc_min(elements, k, x)
    print(result)
全部评论
第二题为啥用set,我用一个freq数组记录a里每个元素出现的次数, 然后一个for loop从a[0] 到a[n]逐个删除,每次删除完以后用freq里第一个值为0的数字做mex
点赞 回复 分享
发布于 2024-08-10 17:39 甘肃
后知后觉,mex的计算那里从后往前计算只需要一个变量保持增长就可以达到O(n)复杂度了😭 import sys def get_mex(elements): mex = [] tempmex = 0 tempele = set() for i in reversed(range(len(elements))): tempele.add(elements[i]) while tempmex in tempele: tempmex += 1 mex.append(tempmex) return reversed(mex) def calc_min(elements, mex, k, x): cost = min(x, k*mex[-1]) for i in reversed(range(len(elements)-1)): cost = min(k*mex[i], x+cost) return cost T = int(sys.stdin.readline().strip()) for _ in range(T): temp = sys.stdin.readline().strip().split() n,k,x = int(temp[0]), int(temp[1]), int(temp[2]) temp = sys.stdin.readline().strip().split() elements = [int(i) for i in temp] mex = get_mex(elements) result = calc_min(elements, mex, k, x) print(result)
点赞 回复 分享
发布于 2024-08-10 14:03 北京
第二题那个mex首次计算得On复杂度,用哈希表,leetcode上有题就是这个。但我光记得最大是n,然后排序做的没过
点赞 回复 分享
发布于 2024-08-10 12:11 上海
点赞 回复 分享
发布于 2024-08-10 12:05 安徽

相关推荐

06-12 16:00
天津大学 Java
牛客30236098...:腾讯坏事做尽,终面挂是最破防的 上次被挂了后我连简历都不刷了
点赞 评论 收藏
分享
评论
1
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务