数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学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
更新于：2022年3月3日
浏览量：140
广告