Readme

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。