阿里笔试 20210319

第一题

$n$ 个人，每个人有一个序号 $arr[i]$，如果这个序号是一个平方数，那么这个人会获奖。
使用修改券，可以使序号加减 1。
求，至少需要多少修改券，可以使一半的人获奖

大概思路就是用sqrt()判断当前数是否是平方数。如果是，则需要修改 0 次；否则需要修改其距离上一个平方数和下一个平方数最小距离次

把所有的距离排序，求前一半的和即可

import math

n = int(input())
arr = list(map(int, input().split(" ")))
dis = [0] * n

for i in range(n):
    l = int(math.sqrt(arr[i]))
    if l * l == arr[i]:
        # 已经是平方数
        dis[i] = 0
    else:
        dis[i] = min(arr[i] - l * l, (l + 1) * (l + 1) - arr[i])

dis.sort()
print(sum(dis[:n//2]))

第二题

有 $n$ 张卡牌，每张分别有两个数值 $a[i]$ 和 $b[i]$。
求使得 $1 \lt i \lt j \lt k \le n$ 且 $a[i] \lt a[j] \lt a[k]$ 时，$b[i] + b[j] + b[k]$ 的最小值。如果不存在输出 $-1$

题目貌似一开始错了（后来把 $\le$ 改成 $\lt$ 了）

大概思路是先把所有的“关系”找出来，使用邻接表存储。
然后使用 DFS 遍历，如果当前和已经超过最大值则剪枝。
（理论上应该还有别的剪枝策略）

n = int(input())
a = list(map(int, input().split(" ")))
b = list(map(int, input().split(" ")))

# r[i][j] 表示 i -> j
r = [
    [] for i in range(n)
]

for i in range(n):
    for j in range(i + 1, n):
        if a[i] < a[j]:
            r[i].append(j)

res = sum(b) +　１


def dfs(cur, sm, l):
    # 当前处理的数是 i，和是 sum， 已处理 l 个数
    global res

    print(cur, sm, l)

    if l >= 2:
        res = min(sm+b[cur], res)
        return

    if sm > res:
        # 剪枝
        return

    for i in r[cur]:
        dfs(i, sm+b[cur], l+1)


for i in arr:
    dfs(n-i-1, 0, 0)

if res == sum(b) + 1:
    res = -1

print(res)