最小堆模拟

lcp71

用并查集把网格拆点、连通、连到超级汇点，统计不与边界连通的封闭区域，算出最大储水量

constexpr int N = 50 * 50 * 4 + 5;

int f[N];

int fd(int x){

if(f[x]!=f[f[x]])

f[x]=fd(f[x]);

return f[x];}

void mg(int x, int y){

x=fd(x);y=fd(y);

if(x!=y)f[x]=y;}

bool co(int x, int y){return fd(x)==fd(y);}

class Solution {

public:

int reservoir(vector<string>& shape) {

int h = shape.size(), w = shape[0].size(), n = h*w*4;

int ans = 0;

iota(f, f+n+1, 0); // n点为超级边界汇点

for (int i = h-1; i >= 0; i--) {

int k = i*w*4;

mg(n, k+1); mg(n, k+w*4-1);

if (i == h-1) for (int j = 0; j < w; k += 4, j++) mg(n, k);

k = i*w*4;

for (int j = 0; j < w; j++, k += 4) {

if (shape[i][j] == '.') mg(k,k+1),mg(k,k+2),mg(k,k+3);

else if (shape[i][j] == 'l') mg(k,k+1),mg(k+3,k+2);

else mg(k, k+3),mg(k+1,k+2);

if (j > 0) mg(k+1, k-1);

}

k = i*w*4;

for (int j = 0; j < w; j++) {

for (int a = 0; a < 4; a++, k++) if (!co(k, n)) ans++;

}

// 检查完本行在实现与上一行之间的连通

k = i*w*4;

if (i > 0) for (int j = 0; j < w; j++, k+=4) mg(k-w*4, k+2);

else for (int j = 0; j < w; j++, k += 4) mg(n, k+2);

}

// 减去封闭的位置

for (int i = 0; i < n; i++) if(!co(i, n)) ans--;

return ans/2;

}

};

lc3296

最小堆，每次选当前耗时最短的工人挖一层山

更新他下次的耗时，直到挖完，最后一次的总耗时就是答案

class Solution {
public:
long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
priority_queue<tuple<long long, long long, int>, vector<tuple<long long, long long, int>>, greater<>> pq;
for (int t : workerTimes) {
pq.emplace(t, t, t);
}

long long ans = 0;
while (mountainHeight--) {
// 工作后总用时，当前工作（山高度降低 1）用时，workerTimes[i]
auto [total, cur, base] = pq.top(); pq.pop();
ans = total;

// 最后一个出堆的 total 即为答案
pq.emplace(total + cur + base, cur + base, base);
}
return ans;
}
};