这篇文章主要围绕[Swift]LeetCode1199.建造街区的最短时间|MinimumTimeToBuildBlocks和城市街区建造者展开，旨在为您提供一份详细的参考资料。我们将全面介绍[Swi
这篇文章主要围绕[Swift] LeetCode1199. 建造街区的最短时间 | Minimum Time To Build Blocks和城市街区建造者展开，旨在为您提供一份详细的参考资料。我们将全面介绍[Swift] LeetCode1199. 建造街区的最短时间 | Minimum Time To Build Blocks的优缺点，解答城市街区建造者的相关问题，同时也会为您带来lc 1199. Minimum Time to Build Blocks、LeetCode - Find minimum time to finish jobs in constraints、LeetCode 1102. Path With Maximum Minimum Value、LeetCode 1167. Minimum Cost to Connect Sticks的实用方法。
本文目录一览：- [Swift] LeetCode1199. 建造街区的最短时间 | Minimum Time To Build Blocks（城市街区建造者）
- lc 1199. Minimum Time to Build Blocks
- LeetCode - Find minimum time to finish jobs in constraints
- LeetCode 1102. Path With Maximum Minimum Value
- LeetCode 1167. Minimum Cost to Connect Sticks
![[Swift] LeetCode1199. 建造街区的最短时间 | Minimum Time To Build Blocks（城市街区建造者）](http://www.gvkun.com/zb_users/upload/2025/02/9a938206-04f9-4ac1-b5f7-7e86596651e71739071240876.jpg "[Swift] LeetCode1199. 建造街区的最短时间 | Minimum Time To Build Blocks（城市街区建造者）")
[Swift] LeetCode1199. 建造街区的最短时间 | Minimum Time To Build Blocks（城市街区建造者）
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（let_us_code）
➤博主域名：https://www.zengqiang.org
➤GitHub 地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/11521675.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
You are given a list of blocks, where blocks[i] = t means that the i-th block needs t units of time to be built. A block can only be built by exactly one worker.
A worker can either split into two workers (number of workers increases by one) or build a block then go home. Both decisions cost some time.
The time cost of spliting one worker into two workers is given as an integer split. Note that if two workers split at the same time, they split in parallel so the cost would be split.
Output the minimum time needed to build all blocks.
Initially, there is only one worker.
Example 1:
Input: blocks = [1], split = 1
Output: 1
Explanation: We use 1 worker to build 1 block in 1 time unit.
Example 2:
Input: blocks = [1,2], split = 5
Output: 7
Explanation: We split the worker into 2 workers in 5 time units then assign each of them to a block so the cost is 5 + max(1, 2) = 7.
Example 3:
Input: blocks = [1,2,3], split = 1
Output: 4
Explanation: Split 1 worker into 2, then assign the first worker to the last block and split the second worker into 2.
Then, use the two unassigned workers to build the first two blocks.
The cost is 1 + max(3, 1 + max(1, 2)) = 4.
Note:
1 <= blocks.length <= 10001 <= blocks[i] <= 10^51 <= split <= 100
你是个城市规划工作者，手里负责管辖一系列的街区。在这个街区列表中 blocks[i] = t 意味着第 i 个街区需要 t 个单位的时间来建造。
由于一个街区只能由一个工人来完成建造。
所以，一个工人要么需要再召唤一个工人（工人数增加 1）；要么建造完一个街区后回家。这两个决定都需要花费一定的时间。
一个工人再召唤一个工人所花费的时间由整数 split 给出。
注意：如果两个工人同时召唤别的工人，那么他们的行为是并行的，所以时间花费仍然是 split。
最开始的时候只有 一个 工人，请你最后输出建造完所有街区所需要的最少时间。
示例 1：
输入：blocks = [1], split = 1
输出：1
解释：我们使用 1 个工人在 1 个时间单位内来建完 1 个街区。示例 2：
输入：blocks = [1,2], split = 5
输出：7
解释：我们用 5 个时间单位将这个工人分裂为 2 个工人，然后指派每个工人分别去建造街区，从而时间花费为 5 + max(1, 2) = 7示例 3：
输入：blocks = [1,2,3], split = 1
输出：4
解释：
将 1 个工人分裂为 2 个工人，然后指派第一个工人去建造最后一个街区，并将第二个工人分裂为 2 个工人。
然后，用这两个未分派的工人分别去建造前两个街区。
时间花费为 1 + max(3, 1 + max(1, 2)) = 4
提示：
1 <= blocks.length <= 10001 <= blocks[i] <= 10^51 <= split <= 100
优先队列
1 class Solution {
2 func minBuildTime(_ blocks: [Int], _ split: Int) -> Int {
3 var pq = PriorityQueue<Int> { $0 < $1 }
4 for v in blocks
5 {
6 pq.push(v)
7 }
8 while(pq.count >= 2)
9 {
10 let x:Int = pq.pop()!
11 let y:Int = pq.pop()!
12 pq.push(y + split)
13 }
14 return pq.pop() ?? 0
15 }
16 }
17
18 public struct PriorityQueue<T> {
19 fileprivate var heap: Heap<T>
20 public init(sort: @escaping (T, T) -> Bool) {
21 heap = Heap(sort: sort)
22 }
23
24 public var isEmpty: Bool {
25 return heap.isEmpty
26 }
27
28 public var count: Int {
29 return heap.count
30 }
31
32 public func peek() -> T? {
33 return heap.peek()
34 }
35
36 public mutating func push(_ element: T) {
37 heap.insert(element)
38 }
39
40 public mutating func pop() -> T? {
41 return heap.remove()
42 }
43
44 public mutating func changePriority(index i: Int, value: T) {
45 return heap.replace(index: i, value: value)
46 }
47 }
48
49 extension PriorityQueue where T: Equatable {
50 public func index(of element: T) -> Int? {
51 return heap.index(of: element)
52 }
53 }
54
55 public struct Heap<T> {
56 var nodes = [T]()
57
58 private var orderCriteria: (T, T) -> Bool
59
60 public init(sort: @escaping (T, T) -> Bool) {
61 self.orderCriteria = sort
62 }
63
64 public init(array: [T], sort: @escaping (T, T) -> Bool) {
65 self.orderCriteria = sort
66 configureHeap(from: array)
67 }
68
69 private mutating func configureHeap(from array: [T]) {
70 nodes = array
71 for i in stride(from: (nodes.count/2-1), through: 0, by: -1) {
72 shiftDown(i)
73 }
74 }
75
76 public var isEmpty: Bool {
77 return nodes.isEmpty
78 }
79
80 public var count: Int {
81 return nodes.count
82 }
83
84 @inline(__always) internal func parentIndex(ofIndex i: Int) -> Int {
85 return (i - 1) / 2
86 }
87
88 @inline(__always) internal func leftChildIndex(ofIndex i: Int) -> Int {
89 return 2*i + 1
90 }
91
92 @inline(__always) internal func rightChildIndex(ofIndex i: Int) -> Int {
93 return 2*i + 2
94 }
95
96 public func peek() -> T? {
97 return nodes.first
98 }
99
100 public mutating func insert(_ value: T) {
101 nodes.append(value)
102 shiftUp(nodes.count - 1)
103 }
104
105 public mutating func insert<S: Sequence>(_ sequence: S) where S.Iterator.Element == T {
106 for value in sequence {
107 insert(value)
108 }
109 }
110
111 public mutating func replace(index i: Int, value: T) {
112 guard i < nodes.count else { return }
113
114 remove(at: i)
115 insert(value)
116 }
117
118 @discardableResult public mutating func remove() -> T? {
119 guard !nodes.isEmpty else { return nil }
120
121 if nodes.count == 1 {
122 return nodes.removeLast()
123 } else {
124 let value = nodes[0]
125 nodes[0] = nodes.removeLast()
126 shiftDown(0)
127 return value
128 }
129 }
130
131 @discardableResult public mutating func remove(at index: Int) -> T? {
132 guard index < nodes.count else { return nil }
133
134 let size = nodes.count - 1
135 if index != size {
136 nodes.swapAt(index, size)
137 shiftDown(from: index, until: size)
138 shiftUp(index)
139 }
140 return nodes.removeLast()
141 }
142
143 internal mutating func shiftUp(_ index: Int) {
144 var childIndex = index
145 let child = nodes[childIndex]
146 var parentIndex = self.parentIndex(ofIndex: childIndex)
147
148 while childIndex > 0 && orderCriteria(child, nodes[parentIndex]) {
149 nodes[childIndex] = nodes[parentIndex]
150 childIndex = parentIndex
151 parentIndex = self.parentIndex(ofIndex: childIndex)
152 }
153
154 nodes[childIndex] = child
155 }
156
157 internal mutating func shiftDown(from index: Int, until endIndex: Int) {
158 let leftChildIndex = self.leftChildIndex(ofIndex: index)
159 let rightChildIndex = leftChildIndex + 1
160
161 var first = index
162 if leftChildIndex < endIndex && orderCriteria(nodes[leftChildIndex], nodes[first]) {
163 first = leftChildIndex
164 }
165 if rightChildIndex < endIndex && orderCriteria(nodes[rightChildIndex], nodes[first]) {
166 first = rightChildIndex
167 }
168 if first == index { return }
169
170 nodes.swapAt(index, first)
171 shiftDown(from: first, until: endIndex)
172 }
173
174 internal mutating func shiftDown(_ index: Int) {
175 shiftDown(from: index, until: nodes.count)
176 }
177
178 }
179
180 extension Heap where T: Equatable {
181
182 public func index(of node: T) -> Int? {
183 return nodes.firstIndex(where: { $0 == node })
184 }
185
186 @discardableResult public mutating func remove(node: T) -> T? {
187 if let index = index(of: node) {
188 return remove(at: index)
189 }
190 return nil
191 }
192 }
lc 1199. Minimum Time to Build Blocks
简直精妙。
哈夫曼编码？
我用的是dp，这种区间dp的时间复杂度是真的难算！状态转移方程为n的区间dp时间都算作n^3吧。
先把任务从长到短排序，然后看worker在那一层要细分多少？就是位置i和员工数n的dp转移。
但是可以贪心！！！！！！！！！！！！每次都是把时间最短的放在最后，而且这两个必然同父，合体后与其他点没有任何差异，继续找最短的合体。
dp代码（python过不了，c++可以）：
class Solution:
def minBuildTime(self, ns, l) -> int:
dp={}
ns.sort(reverse=True)
mx=l*len(ns)*ns[0]
def get(i,n):
if i==len(ns):
return 0
if n==0:
return mx
lst = len(ns) - i
if n >= lst:
return ns[i]
if (i,n) in dp:
return dp[(i,n)]
ans=max(ns[i],get(i+1,n-1))
ans=min(ans,l+get(i,n*2))
dp[(i,n)]=ans
return ans
# for i in reversed(range(len(ns))):
# lst=len(ns)-i
# for j in range(1,lst+1):
# get(i,j)
x=get(0,1)
return x
LeetCode - Find minimum time to finish jobs in constraints
非常值得看的一题啦！和 MIT Quiz 中的那个 network flow 题（Maze Marathonor，在 Algorithm - Network Flow 那篇博客里）过程很相似，过程都是：
1. 算出个最长的可能时间 maxTime。
2. 设计个 boolean isPossible（k）的函数，输入 k 是个时间值，意思是，这个函数用来检测 problem 可不可以在时间 k 内完成。
3. 在 [0, maxTime] 内进行 binary search，在 BS 的过程中每次都对 mid 进行 isPossible（mid），直到最后找到最小的可能时间。
Find minimum time to finish all jobs with given constraints
4.3
Given an array of jobs with different time requirements. There are K identical assignees available and we are also given how much time an assignee takes to do one unit of job. Find the minimum time to finish all jobs with following constraints.
- An assignee can be assigned only contiguous jobs. For example, an assignee cannot be assigned jobs 1 and 3, but not 2.
- Two assignees cannot share (or co-assigned) a job, i.e., a job cannot be partially assigned to one assignee and partially to other
// C++ program to find minimum time to finish all jobs with
// given number of assignees
#include<bits/stdc++.h>
using namespace std;
// Utility function to get maximum element in job[0..n-1]
int getMax(int arr[], int n)
{
int result = arr[0];
for (int i=1; i<n; i++)
if (arr[i] > result)
result = arr[i];
return result;
}
// Returns true if it is possible to finish jobs[] within
// given time ''time''
bool isPossible(int time, int K, int job[], int n)
{
// cnt is count of current assignees required for jobs
int cnt = 1;
int curr_time = 0; // time assigned to current assignee
for (int i = 0; i < n;)
{
// If time assigned to current assignee exceeds max,
// increment count of assignees.
if (curr_time + job[i] > time) {
curr_time = 0;
cnt++;
}
else { // Else add time of job to current time and move
// to next job.
curr_time += job[i];
i++;
}
}
// Returns true if count is smaller than k
return (cnt <= K);
}
// Returns minimum time required to finish given array of jobs
// k --> number of assignees
// T --> Time required by every assignee to finish 1 unit
// m --> Number of jobs
int findMinTime(int K, int T, int job[], int n)
{
// Set start and end for binary search
// end provides an upper limit on time
int end = 0, start = 0;
for (int i = 0; i < n; ++i)
end += job[i];
int ans = end; // Initialize answer
// Find the job that takes maximum time
int job_max = getMax(job, n);
// Do binary search for minimum feasible time
while (start <= end)
{
int mid = (start + end) / 2;
// If it is possible to finish jobs in mid time
if (mid >= job_max && isPossible(mid, K, job, n))
{
ans = min(ans, mid); // Update answer
end = mid - 1;
}
else
start = mid + 1;
}
return (ans * T);
}
// Driver program
int main()
{
int job[] = {10, 7, 8, 12, 6, 8};
int n = sizeof(job)/sizeof(job[0]);
int k = 4, T = 5;
cout << findMinTime(k, T, job, n) << endl;
return 0;
}
LeetCode 1102. Path With Maximum Minimum Value
原题链接在这里：https://leetcode.com/problems/path-with-maximum-minimum-value/
题目：
Given a matrix of integers A with R rows and C columns, find the maximum score of a path starting at [0,0] and ending at [R-1,C-1].
The score of a path is the minimum value in that path. For example, the value of the path 8 → 4 → 5 → 9 is 4.
A path moves some number of times from one visited cell to any neighbouring unvisited cell in one of the 4 cardinal directions (north, east, west, south).
Example 1:
Input: [[5,4,5],[1,2,6],[7,4,6]]
Output: 4
Explanation:
The path with the maximum score is highlighted in yellow.
Example 2:
Input: [[2,2,1,2,2,2],[1,2,2,2,1,2]]
Output: 2Example 3:
Input: [[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]]
Output: 3Note:
1 <= R, C <= 1000 <= A[i][j] <= 10^9
题解：
From A[0][0], put element with index into maxHeap, sorted by element. Mark it as visited.
When polling out the currrent, check its surroundings. If not visited before, put it into maxHeap.
Until we hit the A[m-1][n-1].
Time Complexity: O(m*n*logmn). m = A.length. n = A[0].length. maxHeap add and poll takes O(logmn).
Space: O(m*n).
AC Java:
1 class Solution {
2 int [][] dirs = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
3
4 public int maximumMinimumPath(int[][] A) {
5 int m = A.length;
6 int n = A[0].length;
7
8 PriorityQueue<int []> maxHeap =
9 new PriorityQueue<int []>((a, b) -> b[2] - a[2]);
10 maxHeap.add(new int[]{0, 0, A[0][0]});
11 boolean [][] visited = new boolean[m][n];
12 visited[0][0] = true;
13
14 int res = A[0][0];
15 while(!maxHeap.isEmpty()){
16 int [] cur = maxHeap.poll();
17 res = Math.min(res, cur[2]);
18 if(cur[0]==m-1 && cur[1]==n-1){
19 return res;
20 }
21
22 for(int [] dir : dirs){
23 int x = cur[0] + dir[0];
24 int y = cur[1] + dir[1];
25 if(x<0 || x>=m ||y<0 || y>=n || visited[x][y]){
26 continue;
27 }
28
29 visited[x][y] = true;
30 maxHeap.add(new int[]{x, y, A[x][y]});
31 }
32 }
33
34 return res;
35 }
36 }
LeetCode 1167. Minimum Cost to Connect Sticks
原题链接在这里：https://leetcode.com/problems/minimum-cost-to-connect-sticks/
题目：
You have some sticks with positive integer lengths.
You can connect any two sticks of lengths X and Y into one stick by paying a cost of X + Y. You perform this action until there is one stick remaining.
Return the minimum cost of connecting all the given sticks into one stick in this way.
Example 1:
Input: sticks = [2,4,3]
Output: 14Example 2:
Input: sticks = [1,8,3,5]
Output: 30Constraints:
1 <= sticks.length <= 10^41 <= sticks[i] <= 10^4
题解：
Find the routine that add the two smallest first, then largest repeated the least times.
Use min heap to get two 2 smallest values, merge them and add merged back to min heap unitl there is only one stick in min heap.
Time Complexity: O(nlogn). n = sticks.length.
Space: O(n).
AC Java:
1 class Solution {
2 public int connectSticks(int[] sticks) {
3 if(sticks == null || sticks.length < 2){
4 return 0;
5 }
6
7 PriorityQueue<Integer> minHeap = new PriorityQueue<>();
8 for(int num : sticks){
9 minHeap.add(num);
10 }
11
12 int res = 0;
13 while(minHeap.size() > 1){
14 int merge = minHeap.poll() + minHeap.poll();
15 res += merge;
16 minHeap.add(merge);
17 }
18
19 return res;
20 }
21 }
今天关于[Swift] LeetCode1199. 建造街区的最短时间 | Minimum Time To Build Blocks和城市街区建造者的介绍到此结束，谢谢您的阅读，有关lc 1199. Minimum Time to Build Blocks、LeetCode - Find minimum time to finish jobs in constraints、LeetCode 1102. Path With Maximum Minimum Value、LeetCode 1167. Minimum Cost to Connect Sticks等更多相关知识的信息可以在本站进行查询。
本文标签：
![[转帖]Ubuntu 安装 Wine方法（ubuntu如何安装wine）](https://www.gvkun.com/zb_users/cache/thumbs/4c83df0e2303284d68480d1b1378581d-180-120-1.jpg)
