美团21.9.25笔试代码
第一题：旅游路线 100%
import os
T = int(input())
while T > 0:
T-=1
x = input().split(' ')
x = [int(i) for i in x]
n, m, k = x[0], x[1], x[2]
mm = [[0]*n for i in range(n)]
for i in range(m):
x = input().split(' ')
x = [int(j) for j in x]
u, v = x[0], x[1]
mm[u-1][v-1], mm[v-1][u-1] = 1, 1
km = input().split(' ')
km = [int(i) for i in km]
result = "YES"
for i in range(len(km)-1):
u, v = km[i], km[i+1]
if mm[u-1][v-1] == 1:
continue
else:
result = 'NO'
break
print(result)
第二题：立方碑 100%
import os
def digui(a, pos, m, val, sm):
if pos >= len(a):
return False
if val == sm:
return True
re = digui(a, pos+1, m, val, sm)
if re:
return re
if m > 0:
sm -= a[pos]
sm += a[pos] ** 3
if val == sm:
return True
else:
return digui(a, pos+1, m-1, val, sm)
return False
T = int(input())
while T > 0:
T-=1
x = input().split(' ')
x = [int(i) for i in x]
n, m, k = x[0], x[1], x[2]
a = input().split(' ')
a = [int(j) for j in a]
result = digui(a, 0, m, k, sum(a))
if result:
print("YES")
else:
print('NO')
第三题：水桶效应 100%
import os
x = input().split(' ')
x = [int(i) for i in x]
n, m = x[0], x[1]
a = input().split(' ')
a = [int(j) for j in a]
a = sorted(a)
result = a[0]
pos = 0
for i in range(n-1):
gap = a[i+1] - a[i]
if gap == 0:
continue
if m <(i+1):
break
high = min(gap, int(m/(i+1)))
m -= high * (i+1)
result = a[i] + high
pos = i
if m > 0 and pos == (n-2):
high = int(m/n)
result = a[-1] + high
print(int(result)) 第四题：分小组，求最小极值 36% TLE
import os
global result
result = 1e18
def digui(a, pos, m, cur_res):
global result
if pos >= len(a):
result = min(result, cur_res)
return
n = len(a)
if m == 0:
return
if pos + m >= n:
result = min(result, cur_res)
return
mx = n - pos -m +1
for i in range(1, mx+1):
cur_a = a[pos:pos + i]
cur_res += max(cur_a) - min(cur_a)
digui(a, pos +i, m-1, cur_res)
x = input().split(' ')
x = [int(i) for i in x]
n, m = x[0], x[1]
a = input().split(' ')
a = [int(j) for j in a]
digui(a, 0, m, 0)
print(result)
