贪心|最小生成树

lc3218

“高费用的线段越早切越好”

如果切晚了会有增加segment的风险，而cost最大线段增加的总cost也最多

class Solution {
public:
int minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut)

{
// 存储切割成本和类型，pair第一个值为成本，第二个值0代表水平(H)、1代表垂直(V)
vector<pair<int, int>> cuts;
for (int cost : horizontalCut) {
cuts.emplace_back(cost, 0);
}
for (int cost : verticalCut) {
cuts.emplace_back(cost, 1);
}
// 按成本从大到小排序
sort(cuts.begin(), cuts.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
return a.first > b.first;
});

int horizontalSegments = 1, verticalSegments = 1;
int ret = 0;
for (auto& cut : cuts) {
int cost = cut.first;
int type = cut.second;
if (type == 0) { // 水平切割
ret += cost * horizontalSegments;
verticalSegments++;
} else { // 垂直切割
ret += cost * verticalSegments;
horizontalSegments++;
}
}
return ret;
}
};

最小生成树法

不是真的要写最小生成树，是为了证明采用这种贪心策略是“正确的”，写出来的代码是等价的....

把这个题目转成最小生成树模型，那么正确性就证明完毕了