有一個長度為 n 的由 0 和 1 組成的字符串 s，你需要用最少的步數(shù)將其變成只包含 0 的字符串。在每一步中，你可以選擇任意一個子串，并將其中所有 1 都反轉為 0。你需要輸出最少的步數(shù)。
例如，對于字符串 s = “110101”，你可以進行如下步驟：
第一步：反轉從第 1 個字符到第 3 個字符的子串 “110”，得到字符串 “000101”。
第二步：反轉從第 1 個字符到第 6 個字符的子串 “000101”，得到字符串 “000000”。
因此，最少的步數(shù)為 2。
輸入的第一行包含一個字符串 s，長度不超過 1 0 5 10^5 105。
輸出格式輸出一個整數(shù)，表示最少的步數(shù)。
輸入樣例
重慶分公司
重慶分公司
1101012請在下面編寫你的 C++ 代碼來解決這道題目：
#include#includeusing namespace std;
int main() {// 讀入字符串 s
string s;
cin >>s;
// 計算最少的步數(shù)
int steps = 0;
// 在此處編寫你的代碼
// 輸出結果
cout<< steps<< endl;
return 0;
}
這道題目的算法設計是使用前綴和數(shù)組來計算最少的步數(shù)。
首先，我們從前往后遍歷字符串 s，并計算出前綴和數(shù)組 prefix。前綴和數(shù)組的定義是，對于字符串 s，前綴和數(shù)組為 a，則 a[i] 表示 s[1] 到 s[i] 中 1 的數(shù)量。
然后，對于每一個字符，我們進行如下操作：
如果當前字符是 1，則將步數(shù)加 1。
否則，枚舉以當前字符為起點的子串，并計算出它中 1 的數(shù)量。然后用這個數(shù)量來更新答案。
這樣的時間復雜度是
O
(
n
2
)
O(n^2)
O(n2)，因為我們對于每一個字符都枚舉了它的子串。
但是，我們可以使用前綴和數(shù)組來優(yōu)化這個算法。使用前綴和數(shù)組，我們可以在 O ( 1 ) O(1) O(1)的時間內(nèi)計算出任意一個子串中 1 的數(shù)量。因此，我們可以將時間復雜度優(yōu)化到 O ( n ) O(n) O(n)。
下面是 c++ 代碼實現(xiàn)：
#include#includeusing namespace std;
int main() {// 讀入字符串 s
string s;
cin >>s;
int n = s.size();
// 計算前綴和數(shù)組
int prefix[n + 1];
prefix[0] = 0;
for (int i = 1; i<= n; i++) {prefix[i] = prefix[i - 1] + (s[i - 1] == '1');
}
// 計算最少的步數(shù)
int steps = 0;
for (int i = 0; i< n; i++) {// 如果當前字符是 1，則將步數(shù)加 1
if (s[i] == '1') { steps++;
}
// 否則，枚舉以當前字符為起點的子串
else { for (int j = i + 1; j<= n; j++) {// 計算子串中 1 的數(shù)量
int ones = prefix[j] - prefix[i];
// 更新答案
steps = min(steps, ones);
}
}
}
// 輸出結果
cout<< steps<< endl;
return 0;
}
上面的代碼實現(xiàn)了狀態(tài)轉移方程的過程。
注意：
矩陣的行和列都是從 1 開始編號的，所以要注意初始化和轉移的時候數(shù)組下標的邊界。
在轉移的時候，需要考慮使用道具的情況。
海神波塞冬擁有著神奇的能力，他能夠將一個人的智慧轉化成數(shù)字，并將這個數(shù)字存儲在一個無序數(shù)組中。但是，有一天，海神波塞冬收到了一個神秘的任務，要求他從這個無序數(shù)組中找出最小的 k 個數(shù)，并將它們存儲在另一個數(shù)組中。
題目描述給定一個無序數(shù)組 a 和整數(shù) k，你需要在 a 中找出最小的 k 個數(shù)，并將它們存儲在另一個數(shù)組 b 中。
例如，對于數(shù)組 [3, 4, 1, 2, 5] 和 k = 3，你可以進行如下操作：
第一步：找出數(shù)組中最小的數(shù)字 1，將其存儲在另一個數(shù)組 b 中。
第二步：找出數(shù)組中第二小的數(shù)字 2，將其存儲在另一個數(shù)組 b 中。
第三步：找出數(shù)組中第三小的數(shù)字 3，將其存儲在另一個數(shù)組 b 中。
因此，最后得到的另一個數(shù)組 b 為 [1, 2, 3]。
請在下面編寫你的 C++ 代碼來解決這道題目：
#include#include
using namespace std;
int main() {// 讀入數(shù)組 a 和 k
int a[10], k;
for (int i = 0; i< 10; i++) {cin >>a[i];
}
cin >>k;
// 計算最小的 k 個數(shù)并存儲在另一個數(shù)組 b 中
int b[k];
// 在此處編寫你的代碼
// 輸出結果
for (int i = 0; i< k; i++) {cout<< b[i]<< " ";
}
cout<< endl;
return 0;
}
請注意，你的算法的時間復雜度應該盡可能低。
輸入格式第一行包含整數(shù) n，表示數(shù)組 a 的長度。
第二行包含 n 個整數(shù)，依次為數(shù)組 a 的元素。
第三行包含整數(shù) k。
輸出格式輸出一行，包含 k 個整數(shù)，依次為數(shù)組 b 中的元素。
輸入樣例5
3 4 1 2 5
31 2 3這道題的題意是，給定一個無序數(shù)組 a 和整數(shù) k，你需要在 a 中找出最小的 k 個數(shù)，并將它們存儲在另一個數(shù)組 b 中。
解題思路：
一種方法是使用排序算法將數(shù)組 a 排序，然后直接取前 k 個數(shù)即可。時間復雜度為 O ( n l o g n ) O(nlogn) O(nlogn)。
另一種方法是使用堆來解決這道題。我們可以將數(shù)組 a 中的數(shù)字插入到一個大根堆中，然后每次取出堆頂元素，將其存儲在數(shù)組 b 中。這樣，當我們?nèi)〕隽?k 個數(shù)字之后，堆中剩余的數(shù)字就是最小的 k 個數(shù)字。因此，我們可以在每次插入元素之前檢查堆的大小，如果堆的大小超過 k，就將堆頂元素彈出。
這種方法的時間復雜度為 O ( n l o g k ) O(nlogk) O(nlogk)，要比前一種方法更優(yōu)。
下面是使用堆來解決這道題的 C++ 代碼：
#include#include
#includeusing namespace std;
int main() {// 讀入數(shù)組 a 和 k
int n, k;
cin >>n;
int a[n];
for (int i = 0; i< n; i++) {cin >>a[i];
}
cin >>k;
// 計算最小的 k 個數(shù)并存儲在另一個數(shù)組 b 中
int b[k];
priority_queue, greater>q;
for (int i = 0; i< n; i++) {q.push(a[i]);
if (q.size() >k) { q.pop();
}
}
for (int i = k - 1; i >= 0; i--) {b[i] = q.top();
q.pop();
}
// 輸出結果
for (int i = 0; i< k; i++) {cout<< b[i]<< " ";
}
cout<< endl;
return 0;
}
這就是使用堆來解決本題的解法。
你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
