각 행에 3개의 값이 있는 작업 행렬이 있다고 가정합니다. 또 다른 값 k가 있습니다. 태스크에서 k개의 행을 선택하고 S라고 불러야 다음 합계가 최소화되고 합계가 다음과 같이 반환됩니다. 최대값:(S[0, 0], S[1, 0], ...S[k - 1, 0]) + 최대 (S[0, 1], S[1, 1], ...S[k - 1, 1]) + 최대 (S[0, 2], S[1, 2], ...S[k - 1, 2]) 다음과 같이 말할 수도 있습니다. 3개의 열 각각은 비용에 기여하고 S에서 해당 열의 최대값을 취하여 계산됩니다. 목록은 0입니다.
따라서 입력이 task =[[2, 3, 3], [4, 5, 2], [4, 2, 3] ], k =2인 경우 출력은 10이 됩니다. 첫 번째 행과 마지막 행. 총합은 S =[[2,3,3],[4,2,3]] max(S[0,0], S[1,0]) =4 + max(S[0,1]입니다. ], S[1,1]) =3 + 최대(S[0,2], S[1,2]) =3 =10
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- util() 함수를 정의합니다. B가 걸립니다.
- 목록 B 정렬
- yheap :=범위 0에서 K-1의 각 i에 대해 -B[i, 1]이 있는 목록
- 힙업
- ans :=B[K - 1, 0] + (-yheap[0])
- K 범위에서 B 크기 사이의 i에 대해 다음을 수행합니다.
- x :=B[i, 0]
- yheap을 -B[i,1]로 교체
- yheap의 설정 크기는 K와 동일합니다.
- y :=-yheap[0]
- ans :=ans 및 x + y의 최소값
- 반환
- 메인 방법에서 다음을 수행하십시오 -
- A가 비어 있거나 K가 0이면
- 0을 반환
- 목록 A 정렬
- B :=범위 0에서 K-1까지의 각 i에 대해 [A[i, 1], A[i, 2]] 쌍의 목록을 만듭니다.
- ans :=A[K - 1, 0] + B의 각 (y, z)에 대한 최대 y + B의 각(y, z)에 대한 최대 z
- K 범위에서 A 크기까지의 i에 대해
- B에 [A[i][1], A[i][2]] 삽입
- ans =ans 및 A[i, 0] + util(B)의 최소값
- 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
import heapq class Solution: def solve(self, A, K): if not A or not K: return 0 def util(B): B.sort() yheap = [-B[i][1] for i in range(K)] heapq.heapify(yheap) ans = B[K - 1][0] + (-yheap[0]) for i in range(K, len(B)): x = B[i][0] heapq.heappushpop(yheap, -B[i][1]) assert len(yheap) == K y = -yheap[0] ans = min(ans, x + y) return ans A.sort() B = [[A[i][1], A[i][2]] for i in range(K)] ans = A[K - 1][0] + max(y for y, z in B) + max(z for y, z in B) for i in range(K, len(A)): B.append([A[i][1], A[i][2]]) ans = min(ans, A[i][0] + util(B)) return ans ob = Solution() tasks = [ [2, 3, 3], [4, 5, 2], [4, 2, 3] ] k = 2 print(ob.solve(tasks, k))
입력
tasks = [ [2, 3, 3], [4, 5, 2], [4, 2, 3] ], k = 2
출력
10