資料結構
網路
關係資料庫管理系統 (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
廣告