美团21.9.25笔试代码

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)
    

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')
    

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))

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)