0408微众笔试复盘

超、凢脫俗 2023-07-24 08:40 70阅读 0赞

博主0408的时候参加了微众笔试，感觉题目不难但是没有全AC。下来复盘的时候感觉自己考试的时候可能是脑子进水了，很多显而易见的情况都没考虑到。果然这段时间沉迷小说游戏综艺让脑子也变得安逸了。闲话不再续，下面正式复盘。

### 1 分礼物 ###

> 有n位小朋友去小明家里拜年，小明准备了m份礼物。小明想把所有礼物平均分给每个小朋友，每个小朋友得到相同个数的礼物。但是m未必能被n整除，小明可以使用以下两种操作任意多次（两种操作可以同时使用）。  
> 1、 给其中一个小朋友发红包，收到红包的小朋友会离开小明家。每个红包需要花费a元。  
> 2、 购买一个新礼物，每个礼物价值为b元。  
> 问小明最少花费多少元，才能使得所有礼物可以被剩下的小朋友平分。  
> 第一行输入四个整数n,m,a,b（1≤n,m,a,b≤100）。  
> 输出最少花费。  
> 输入样例1  
> 7 5 10 100  
> 20  
> 输入样例2  
> 2 2 10 10  
> 输出样例2  
> 0  
> 输入样例3  
> 3 1 10 10  
> 输出样例3  
> 20  
> 样例解释  
> 样例一发两个红包。样例二不需要任何操作。样例三买两个新礼物，或者发两个红包，或者发一个红包买一个新礼物。

由于被测试用例糊住了，先入为主的认为送礼物的数量等于送走的朋友数，实际上这种等式关系只有m<n或其他特定情况才成立。也是沾了测试用例的光，这种想法居然也A了91。  
此题的point恰恰在于**送礼物的数量不一定等于送走的朋友数**，假设送走了 i i i个小朋友，买了 k k k个新礼物，题目要求 ( m + k ) % ( n − i ) = = 0 (m+k)\\%(n-i)==0 (m\+k)%(n−i)==0，且 a i + k b ai+kb ai\+kb最小。可以遍历做。

def test(n,m,a,b):
        min = None
        if m%n == 0:
            return 0
        else:
            # 假设红包送走i个小朋友
            for i in range(n):
                # 剩下n-i个小朋友中没有礼物的小朋友
                if n==i:
                    res = n*a
                else:
                    if m%(n-i)==0:
                        res = i*a
                    else:
                        tmp = (n-i) - m%(n-i)
                        res = tmp * b + i*a
                if not min or min>res:
                    min = res
            return min

### 2 回文游戏 ###

> Cassidy和Eleanore是一对好朋友，她们经常会一起玩游戏。某一天她们玩了一个回文游戏。游戏规则是这样的：给出一个仅包含小写字母的字符串S，在每一个人的回合中，她们会进行两个操作：  
> 1 尝试重新排列这个字符串，如果可以把这个字符串排列成回文字符串，则立即获胜。  
> 2 否则，她们必须删掉字符串中的一个字符。  
> 已知，Cassidy先手，在两个人都采取最佳策略的情况下，谁可以获胜。  
> 输入第一行仅包含一个正整数t，表示数据组数，(t<=10)  
> 接下来有t行，每行有一个字符串S，表示一组测试数据。(|S|<=1000)  
> 对于每组数据输出一行，如果Cassidy获胜，则输出Cassidy，否则输出Eleanore  
> 输入样例  
> 2  
> aba  
> ab  
> 输出样例  
> Cassidy  
> Eleanore

这个题还是比较友好，全ac了。一个字符串若能构成回文串，串中计数为奇数的字符个数不能大于1，否则无法构成字符串。最优策略就是，先检查字符串，若能构成回文串，胜利；若不能，优先将串中计数为偶数的字符删掉一个。

def createDic(s):
            dic = {
        }
            for i in s:
                if i not in dic:
                    dic[i] = 1
                else:
                    dic[i] += 1
            return dic
    
        def testPalin(dic):
            odd_count = 0
            even_count = 0
            for key in dic:
                if dic[key] % 2 == 1:
                    odd_count += 1
                else:
                    even_count += 1
            if odd_count > 1:
                return False
            else:
                return True
    
        def delString(dic):
            # 如果存在偶数，将偶数删成奇数，使奇数尽可能多
            flag = False
            for key in dic:
                if dic[key] > 0 and dic[key]%2 == 0:
                    dic[key] -= 1
                    flag = True
                    break
            # 如果删除失败，没有偶数字符；只能删除奇数字符
            if not flag:
                for key in dic:
                    if dic[key] > 0 and dic[key] % 2 == 1:
                        dic[key] -= 1
                        break
    
    
        def test(s):
            # s:字符串
            dic = createDic(s)
            count = 0
            while True:
                if testPalin(dic):
                    if count%2==0:
                        return 'Cassidy'
                    else:
                        return 'Eleanore'
                else:
                    delString(dic)
                count += 1

### 3 抽卡游戏 ###

> 抽卡是一类类似于博弈的游戏。现在有一种抽卡方式，描述如下：  
> 初始你只有一次抽卡机会。每次抽卡浪费一次抽卡机会，获得一张卡片。这张卡片上有两个数字，第一个数字代表你能获得的钱，第二个数字代表你能获得的额外抽卡次数。额外的抽卡次数是可以累计的。  
> 现在，你知道了卡片的数量，所有的卡片上的数字，以及所有卡片的顺序。你只需要安排一种抽卡顺序，使得你能获得钱数最多。  
> 输入：  
> 第一个行一个数n,代表卡片的数量。 接下来n行，每行用两个数ai,bi描述一张卡片。ai表示抽这张卡能获得的钱数，bi表示抽这张卡能获得的额外抽卡次数。  
> 输出：  
> 一行一个数，代表你能获得的最多钱数。  
> 输入样例  
> 5  
> 0 2  
> 1 1  
> 1 0  
> 1 0  
> 2 0  
> 输出样例  
> 4  
> 对于100%的数据，0≤a\_i,b\_i≤1000,1≤n≤1000。样例解释：按顺序抽第2,1,5,4张卡

此题我的想法是先把有抽卡次数的卡抽了，再按照钱数大小抽卡。看了牛客大家的思路都是类似的，但是我只ac了72。仔细比照了一下代码，实在是发现不出来问题。  
不过：其实可以先把有抽卡次数的全部先消耗掉（即有抽卡次数的卡不参与排序），只排序无抽卡次数，有钱数的卡。  
后来发现可能不是逻辑的问题，而是while循环的判断有误，可能还有count值但是卡已经抽完了，这个时候我的代码会报边界错误。果然笔试时不能再主文件写try…except，否则有错误也不会报出来。

def test(arr):
        arr = sorted(arr,key=lambda x:(x[1],x[0]),reverse=True)
        # arr = sorted(arr, key=lambda x: (-x[0], x[1]))
        print(arr)
        count = 1
        money = 0
        for i in range(len(arr)):
            if count == 0: break
            tmp =arr[i]
            count = count - 1 + tmp[1]
            money = money + tmp[0]
        return money