2018.10.9 美团笔试

发表于 |

总结：共两道算法题（1TLE, 1AC），题型比较有意思，美团还是很有东西的！

1. 外卖满减（36% passed, TLE）

你打开美了么外卖，选择了一家店，你手里有一张满X元减10元的券，店里总共有n种菜，第i种菜一份需要A[i]元，因为你不想吃太多份同一种菜，所以每种菜，你最多只能点一份，现在问你最少需要选择多少元的菜才能使用这张券？

输入描述：
第一行两个正整数n和x，分别表示菜品数量和券的最低使用价格。（1<=n<=100， 1<=X<=10000）
接下来一行包括n个整数，第i个整数表示第i个菜的价格(1 <= A[i] <= 100)

输出描述：
一个整数，表示最少需要选择多少元的菜才能使用这张满X元减10元的券，题目保证有解。

样例输入：
5 20
18 19 17 6 7

样例输出：
23

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 这是只过了36%的code, dfs即使剪枝复杂度还是太大了
from collections import Counter, defaultdict, deque
read = lambda: list(map(int,input().split()))

n,x = read()
a = read()
a.sort(reverse=True)
s = [a[-1]] * n # 后缀和，用作剪枝
for i in range(n-2,-1,-1):
    s[i] = a[i] + s[i+1]

def dfs(total,index,res=[float('inf')]):
    if total >= x:
        res[0] = min(res[0], total)
        return
    if index < n and total + s[index] < x: return
    for i in range(index, n):
        dfs(total + a[i], i+1, res)

res = [float('inf')]
dfs(0,0,res)
print(res[0])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 这是事后写的dp，确实是一个01背包问题，但由于错过了提交时间，也不知道真正通过率怎样
from collections import Counter, defaultdict, deque
read = lambda: list(map(int,input().split()))

n,x = read()
a = read()
v = sum(a) - x # 代表背包容量
dp = [[0]*v for _ in range(n)]
res = 0
for i in range(n):
    for j in range(v):
        if j - a[i] >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i][j-a[i]] + a[i])
        else:
            dp[i][j] = dp[i-1][j]
        res = max(res, dp[i][j])
print(v-res+x)

2. 数的度序列(AC)

在图论中，树是一种简单无向图，其中任意两个顶点间存在唯一一条简单路径，或者说只要没有回路的简单连通图就是树。

在一张简单图中，一个顶点的度数是与其相关联的边的条数，或者说是其邻居的数目。现在给出一个整数序列，你需要判断它是否是某一颗树的度序列

输入描述：
用例包含多组数据；
第一行一个正整数T，表示数据组数
对于每一组数据，第一行包含一个整数n，表示序列的长短，1 <= n <= 10^5
第二行包含n个整数a[i]，a[i]表示第i个顶点的度。 1 <= a[i] <= 10^9

输出描述：
逐行输出判断结果，如果是某个数的度序列，输出‘Yes’，否则输出’No’

样例输入：
2
6
1 1 1 4 2 1
4
1 2 2 3

样例输出：
Yes
No

1
2
3
4
5
6
7
8
9
# 只需要判断度之和是不是边数量的2倍
# 边数量又等于节点数减1
t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    if sum(a) != 2*(n-1): print('No')
    else:
        print('Yes')