2020.9.5

• 美团
• 百度
• 搜狗

美团

津贴兑换：津贴序列，有连续两个一样的x元的津贴可以变成x+1；这样的最后津贴序列是？

输入：序列长度n,序列a
输出：经过变换的序列

列子：

input：
5
[1, 1, 1, 1, 1]

output：3

代码：

n = 5
a = [1, 1, 1, 1, 1]

sum_con = 0
con = -1
while con != 0:
    con = 0
    pre = a[len(a) - 1]
    i = len(a)-2
    while i >= 0:
        if a[i] == pre:
            con += 1
            a[i] = pre + 1
            a.pop(i+1)
        pre = a[i]
        i = i - 1
    sum_con += con
print(sum_con)

百度

买纪念品：纪念品的属性有重量（weight），价格（price），心动值（v），共有n件纪念品；李明有预算k，最多拿m千克的礼物；

输入：第一行，n m k 第2行到n+1行每行为price weight v
输出：不超过预算和不累的情况下，最多能带的纪念品个数

列子：

input：
3 10 1000
100 5 3
50 3 2
300 3 3

output：2

# p,w,v,k,m,n

n,m,k=map(int,input().split())
data= []
for i in range(n):
    p,w,v = map(int,input().split())
    data.append({'p':p,'w':w,'v':v})

data_new = sorted(data, key=lambda x: (-x['v'], x['p']))
cnt = 0
for i in data_new:
    if i['w']< m and i['p']< k:
        cnt += 1
        m = m - i['w']
        k = k - i['p']
    else:
        break
print(cnt)

搜狗

游戏道具兑换礼物：游戏中有道具（A,B,C），任意两个道具可以兑换一个道具，三个不同道具可以兑换一个礼物，求他最多能兑换礼物的个数

输入：A,B,C的个数
输出：最多能兑换礼物的个数

列子：

input： 4 4 2

output：3

# 需要耐心和细心的方法
def test(a,b,c):
    data = [a,b,c]
    cnt = min(data)
    data= [x-cnt for x in data]
    tmp_data = [i for i in data if i > 1]
    while data.count(0) != 3:
        # 没有一个大于1，无法满足兑换条件
        if tmp_data == []:
            return cnt
        # 一个0，两个大于1，这两个各给一个作为兑换
        elif data.count(0)==1 and len(tmp_data) == 2:
            ind_0 = data.index(0)
            data = [x - 2 for x in data]
            cnt += 1
            data[ind_0]=0
            tmp_data = [i for i in data if i > 1]
        # 两个0，一个大于1
        elif data.count(0) == 2:
            # 两个0，一个大于1小于5，不满足兑换条件
            if tmp_data[0] < 5:
                break
            else:
                ind_1 = data.index(tmp_data[0])
                ind_0 = data.index(0)
                data = [x - 5 for x in data]
                data[ind_0] = 0
                data[ind_1] = 0
                cnt += 1
                tmp_data = [i for i in data if i > 1]
        # 一个0，一个1，一个大于1
        elif data.count(0) == 1 and len(tmp_data) == 1:
            # 一个0，一个1，一个大于1但小于3，不满足兑换条件
            if tmp_data[0] < 3:
                return cnt
            # 一个0，一个1，一个大于3
            else:
                ind_1 = data.index(1)
                ind_0 = data.index(0)
                data = [x - 3 for x in data]
                data[ind_0] = 0
                data[ind_1] = 0
                cnt += 1
                tmp_data = [i for i in data if i > 1]
    return cnt


if __name__ == '__main__':
    a,b,c = 4,4,2
    print(test(a, b, c))
    a, b, c = 9, 3, 3
    print(test(a, b, c))
    a, b, c = 5,7, 3
    print(test(a, b, c))