C++程序：求购买二进制字符串所需的最少硬币数

假设我们有三个数字c0、c1和h，以及一个二进制字符串S。我们可以翻转S中的任何位。每次更改需支付h枚硬币。经过一些更改（可能为零）后，我们想要购买该字符串。要购买该字符串，我们必须购买其所有字符。购买位0需要支付c0枚硬币，购买位1需要支付c1枚硬币。我们必须找到购买该字符串所需的最小硬币数。

因此，如果输入类似于c0 = 10；c1 = 100；h = 1；S = "01010"，则输出将为52，因为首先我们更改S中的第2位和第4位，为此支付2枚硬币。现在字符串将变为00000。之后，我们可以购买该字符串，为此支付5⋅10=50枚硬币。支付的硬币总数将为2+50=52。

步骤

为了解决这个问题，我们将遵循以下步骤：

k := 0
n := size of S
for initialize i := 0, when i < n, update (increase i by 1), do:
   if S[i] is same as '0', then:
      k := k + minimum of c0 and (c1 + h)
   Otherwise
      k := k + minimum of (c0 + h) and c1
return k

示例

让我们看看下面的实现以更好地理解：

#include <bits/stdc++.h>
using namespace std;

int solve(int c0, int c1, int h, string S) {
   int k = 0;
   int n = S.size();
   for (int i = 0; i < n; i++) {
      if (S[i] == '0')
         k = k + min(c0, c1 + h);
      else
         k = k + min(c0 + h, c1);
   }
   return k;
}
int main() {
   int c0 = 10;
   int c1 = 100;
   int h = 1;
   string S = "01010";
   cout << solve(c0, c1, h, S) << endl;
}

输入

10, 100, 1, "01010"

输出

52

Arnab Chakraborty

更新于：2022年3月3日

浏览量：140

启动您的职业生涯

完成课程后获得认证

开始学习