小米 09.19 笔试

1. 背包问题，18%，听说是python的问题，改成c++能ac

import sys

def _min(data, N, c):
    n = len(data)
    data.sort(reverse=True)
    res = N
    # print(data)
    def dfs(idx, left):
        nonlocal res
        if res <= c:
            return
        # print(idx, left, res)
if idx >= n or data[idx] > left:
            if left < res:
                res = left
            return
        
        dfs(idx + 1, left - data[idx])
        dfs(idx + 1, left)
    dfs(0, N)
    return res
    

def get(data, N, c):
    if sum(data) + c < N:
        return "NO"
    # nee = N
    min_res = _min(data, N, c)
    # print(min_res)
if c >= min_res:
        return "YES"
    else:
        return "NO"

line = sys.stdin.readline()
# values = map(int, line.split())

T = int(line)

for i in range(T):
    line = sys.stdin.readline()
    values = [int(v) for v in line.split()]
    N, n, c = values
if c >= N:
        print("YES")
        continue
    
    line = sys.stdin.readline()
    values = [int(v) for v in line.split()]
    data = values
    
    print(get(data, N, c))

# 18%

2. 交换数组使得递增或递减，ac

def swap(arr1, arr2, idx):
    arr1[idx], arr2[idx] = arr2[idx], arr1[idx]

def _sort(arr1, arr2):
    _len = len(arr1)
    flag = True
    for i in range(_len):
        if i == 0:
if arr1[i] > arr2[i]:
                swap(arr1, arr2, i)
        else:
if arr1[i] > arr2[i] and arr2[i] >= arr1[i-1]:
                swap(arr1, arr2, i)
            if arr1[i] < arr1[i-1] and arr2[i] >= arr1[i-1]:
                swap(arr1, arr2, i)
            if arr1[i] < arr1[i-1]:
                flag = False
                break
    if flag:
        return True
    
    flag = True
    for i in range(_len):
        if i == 0:
if arr1[i] > arr2[i]:
                swap(arr1, arr2, i)
        else:
if arr1[i] > arr2[i] and arr1[i] <= arr2[i-1]:
                swap(arr1, arr2, i)
if arr2[i] > arr2[i-1] and arr1[i] <= arr2[i-1]:
                swap(arr1, arr2, i)
if arr2[i] > arr2[i-1]:
                flag = False
                break
    return flag
    
import sys

line = sys.stdin.readline()
T = int(line)

for i in range(T):
    line = sys.stdin.readline()
    n = int(line)

    line = sys.stdin.readline()
    arr1 = [int(v) for v in line.split()]

    line = sys.stdin.readline()
    arr2 = [int(v) for v in line.split()]
    
    flag = _sort(arr1, arr2)
    if flag:
        print("YES")
    else:
        print("NO")

# 100%