贝壳第三题健身房最大锻炼值代码,有没有大佬来交流下思路?
rt,有大佬来讨论下么,我这里用堆来解决的这个问题,具体代码如下,有大佬要交流思路的可以私聊我。
#贝壳找房##笔试题目#
import sys import heapq data = [] for a in sys.stdin.readlines(): data.append([int(x) for x in a.strip().split()]) N = data[0][0] X = data[1] P = data[2] E = [2*X[i]+P[i] for i in range(len(X))] heap1 = [] heap2 = [] for i, x in enumerate(E): heapq.heappush(heap1, (-1*x, i)) ptr = -1 res = [] while len(res) != N: if ptr == -1: y, idx = heapq.heappop(heap1) res.append(-1*y) if idx > ptr: ptr = idx for i, x in enumerate(heap1): if x[1] < ptr: heapq.heappush(heap2, (-1*P[x[1]], x[1])) heap1[i] = 0 if 0 in heap1: heap1.remove(0) tmp = [] for x in heap1: if x != 0: heapq.heappush(tmp, x) heap1 = tmp else: if len(heap2) == 0 or (len(heap1) != 0 and -1*heap1[0][0] - 2*X[ptr] > -1*heap2[0][0]): y, idx = heapq.heappop(heap1) res.append(-1*y - 2*X[ptr] + res[-1]) if idx > ptr: ptr = idx #还要将heap1中的所有比ptr位置之前的都要放到ptr2中去 tmp = [] for i, x in enumerate(heap1): if x[1] < ptr: heapq.heappush(heap2, x) heap1[i] = 0 for x in heap1: if x != 0: heapq.heappush(tmp, x) heap1 = tmp else: y, idx = heapq.heappop(heap2) res.append(-1*y + res[-1]) for x in res: print(x)
#贝壳找房##笔试题目#