招行fintech0429三题
邮件说了不要透题，我就不透题吧，参加了的应该都还记得。下面只说思路和代码，供大家参考讨论
A：coins[i][j]保存第i行j个位置金币数量，每行头尾单独讨论
N = int(input()) coins = [] max_coins = 0 for i in range(N): coins.append(list(map(int, input().split()))) if i > 0: for j, c in enumerate(coins[i]): if j == 0: coins[i][j] = coins[i][j] + coins[i-1][j] elif j == i: coins[i][j] = coins[i][j] + coins[i-1][-1] else: coins[i][j] = coins[i][j] + max(coins[i-1][j-1], coins[i-1][j]) max_coins = max(coins[-1]) print(max_coins)
B：用一个字典记录每个人的和座位的对应，然后两个两个遍历整个数组，将其中一个人的配偶换到他身边就可以，注意更新人和座位对应表。算法为什么会是交换次数最少不在这证明了。
n = int(input())
line = list(map(int, input().split()))
idx2seat = {idx:seat for seat, idx in enumerate(line)}
cnt = 0
for i in range(n):
if line[2*i] > line[2*i+1]:
line[2*i], line[2*i+1] = line[2*i+1], line[2*i]
if line[2*i]&1 == 0 and line[2*i+1]-line[2*i] == 1:
continue
if line[2*i]&1 == 0:
idx1, idx2 = line[2*i+1], line[2*i]+1
seat1, seat2 = 2*i+1, idx2seat[line[2*i]+1]
line[seat1], line[seat2] = line[seat2], line[seat1]
idx2seat[idx1], idx2seat[idx2] = seat2, seat1
else:
idx1, idx2 = line[2*i+1], line[2*i]-1
seat1, seat2 = 2*i+1, idx2seat[line[2*i]-1]
line[seat1], line[seat2] = line[seat2], line[seat1]
idx2seat[idx1], idx2seat[idx2] = seat2, seat1
cnt += 1
print(cnt) 从小到大枚举塔高度作为最终塔高m，对于m，有下面四种可能：
1. 塔高为m的塔数量已经大于等于k，直接返回0；
2. 需要将塔高小于m的塔增高至m，使得塔高为m的塔数大于等于k。注意由于每次必须增高最低的塔，在这种情况下终止情况必为：k个高为m的塔，其余原高度小于m的塔被增高至m-1；
3. 需要将塔高大于m的塔降低至m，和2同理；
4. 急需要增高又需要降低，和2，3同理。
通过维护几个变量可以一次遍历：l_cnt，塔高小于m的塔数量，l_cube，将所有塔高小于m的塔全部增高至m需要多加的方块总数；h_cnt，h_cube同理
from collections import Counter
n, k = list(map(int, input().split()))
arr = list(map(int, input().split()))
sum_cube = sum(arr)
h_cnter = Counter(arr)
hs = sorted(h_cnter.keys())
l_cnt, l_cube, l = 0, 0, 0
h_cnt, h_cube = n, sum_cube
min_op = float("inf")
for m in hs:
h_cube -= h_cnt * (m - l)
m_cnt = h_cnter[m]
h_cnt -= m_cnt
l_cube += l_cnt * (m - l)
if m_cnt >= k:
min_op = 0
break
if m_cnt + h_cnt >= k:
min_op = min(min_op, h_cube-(m_cnt+h_cnt-k))
if m_cnt + l_cnt >= k:
min_op = min(min_op, l_cube-(m_cnt+l_cnt-k))
min_op = min(min_op, h_cube+l_cube-(n-k))
l_cnt += m_cnt
l = m
print(min_op)
