Back to Leetcode

Readme

Greedy/3800.Minimum-Cost-to-Make-Two-Binary-Strings-Equal/Readme.md

latest1.0 KB
Original Source

3800.Minimum-Cost-to-Make-Two-Binary-Strings-Equal

本题的关键是注意到cross和swap操作的意义和用处。它们可以同时帮助两处位置配平。

我们考虑A="01",B="10",它们的两个位置都需要修正。如何操作呢?第一种是老老实实用两次flip,就可以将A变成B。第二种就是用一次swap,同样可以将A变成B。这就提醒我们可以收集“A[i]=1,B[i]=0”以及“A[i]=0,B[i]=1”的pairs,每修正这样的一对,我们的代价就是两种策略的较小值:min(2*flipCost, swapCost).

接下来,如果A与B仍有不相同的位置,必然是形如A="11",B="00"(或者反过来)的情况。同样,我们也有两种操作:第一种是老老实实用两次flip,就可以将A变成B。第二种就是用一次cross,再做一次swap,同样可以将A变成B。每修正这样的一对,我们的代价就是两种策略的较小值:min(2*flipCost, swapCost+crossCost).

最后如果仍然有仍有(最多一个)不相等的位置,那么只能再用单次的flip。