블록 목록이 있다고 가정하고 블록[i] =t이면 i번째 블록을 구축하는 데 t 단위 시간이 필요합니다. 블록은 정확히 한 명의 작업자만 만들 수 있습니다. 단일 작업자는 두 작업자로 분할하거나 블록을 만든 다음 집에 갈 수 있습니다. 이 두 가지 결정에는 시간이 걸립니다. 한 작업자를 두 작업자로 나누는 시간 비용은 분할이라는 숫자로 표시됩니다.
따라서 입력이 블록 =[1,2]이고 split =5와 같으면 작업자를 5시간 단위로 2명의 작업자로 분할한 다음 각각을 블록에 할당하여 비용을 절감할 수 있으므로 출력은 7이 됩니다. 5 + 최대 1 및 2 =7입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
하나의 우선순위 큐 pq 정의
-
initialize i :=0의 경우, i <블록 크기일 때 업데이트(i를 1만큼 증가), −
-
블록[i]을 pq에 삽입
-
-
pq의 크기> 1인 동안 −
-
pq에서 요소 삭제
-
x :=pq의 최상위 요소
-
pq에서 요소 삭제
-
split + x를 pq에 삽입
-
-
pq의 맨 위 요소를 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minBuildTime(vector<int>& blocks, int split) {
priority_queue<int, vector<int>, greater<int> > pq;
for (int i = 0; i < blocks.size(); i++)
pq.push(blocks[i]);
while (pq.size() > 1) {
pq.pop();
int x = pq.top();
pq.pop();
pq.push(split + x);
}
return pq.top();
}
};
main(){
Solution ob;
vector<int> v = {1,2};
cout << (ob.minBuildTime(v, 5));
} 입력
{1,2}, 5 출력
7