京东算法笔试 9.11
1. 序列重排
# 序列重排
import sys
from collections import deque
def get_result(arr):
arr = sorted(arr)
q = deque([arr[0]])
l, r = 1, len(arr) - 1
res = 0
while l <= r:
t = [abs(q[0] - arr[l]), abs(q[0] - arr[r]), abs(q[-1] - arr[l]), abs(q[-1] - arr[r])]
for i in range(len(t)):
if max(t) == t[i]:
res += t[i]
if i == 0:
q.appendleft(arr[l])
l += 1
elif i == 1:
q.appendleft(arr[r])
r -= 1
elif i == 2:
q.append(arr[l])
l += 1
else:
q.append(arr[r])
r -= 1
break
print(res)
if __name__=='__main__':
n = int(sys.stdin.readline().strip(' ').strip('\n').strip(' '))
arr = list(map(int, sys.stdin.readline().strip(' ').strip('\n').strip(' ').split(' ')))
get_result(arr)
# get_result([ 2,2,2,1, 5])
2. 依赖 # 依赖
import sys
from collections import deque
def get_result(n,edges,qs):
tree1,tree2 = {},{} # 开 # 关
for i in range(len(edges)):
tree1[i+1] = edges[i][1:]
for to in edges[i][1:]:
if to not in tree2:
tree2[to] =[]
tree2[to].append(i+1)
res = [0]
book = [0 for _ in range(n+10)]
def change1(root): # 开
if book[root]==1:
return
res[0] +=1
book[root]=1
for to in tree1.get(root,[]):
change1(to)
def change2(root):
if book[root]==0:
return
res[0]-=1
book[root] =0
for to in tree2.get(root,[]):
change2(to)
for i in range(len(qs)):
if qs[i][0]==1:
change1(qs[i][1])
else:
change2(qs[i][1])
print(res[0])
if __name__=='__main__':
n,q = list(map(int, sys.stdin.readline().strip(' ').strip('\n').strip(' ').split(' ')))
edges = []
for _ in range(n):
edges.append(list(map(int, sys.stdin.readline().strip(' ').strip('\n').strip(' ').split(' '))))
qs = []
for _ in range(q):
qs.append(list(map(int, sys.stdin.readline().strip(' ').strip('\n').strip(' ').split(' '))))
get_result(n,edges,qs)
# get_result([ 2,2,2,1, 5])
