有一个长度为 n 的由 0 和 1 组成的字符串 s，你需要用最少的步数将其变成只包含 0 的字符串。在每一步中，你可以选择任意一个子串，并将其中所有 1 都反转为 0。你需要输出最少的步数。
例如，对于字符串 s = “110101”，你可以进行如下步骤：
第一步：反转从第 1 个字符到第 3 个字符的子串 “110”，得到字符串 “000101”。
第二步：反转从第 1 个字符到第 6 个字符的子串 “000101”，得到字符串 “000000”。
因此，最少的步数为 2。
输入的第一行包含一个字符串 s，长度不超过 1 0 5 10^5 105。
输出格式输出一个整数，表示最少的步数。
输入样例1101012请在下面编写你的 C++ 代码来解决这道题目：
#include#includeusing namespace std;
int main() {// 读入字符串 s
string s;
cin >>s;
// 计算最少的步数
int steps = 0;
// 在此处编写你的代码
// 输出结果
cout<< steps<< endl;
return 0;
}
这道题目的算法设计是使用前缀和数组来计算最少的步数。
首先，我们从前往后遍历字符串 s，并计算出前缀和数组 prefix。前缀和数组的定义是，对于字符串 s，前缀和数组为 a，则 a[i] 表示 s[1] 到 s[i] 中 1 的数量。
然后，对于每一个字符，我们进行如下操作：
如果当前字符是 1，则将步数加 1。
否则，枚举以当前字符为起点的子串，并计算出它中 1 的数量。然后用这个数量来更新答案。
这样的时间复杂度是
O
(
n
2
)
O(n^2)
O(n2)，因为我们对于每一个字符都枚举了它的子串。
但是，我们可以使用前缀和数组来优化这个算法。使用前缀和数组，我们可以在 O ( 1 ) O(1) O(1)的时间内计算出任意一个子串中 1 的数量。因此，我们可以将时间复杂度优化到 O ( n ) O(n) O(n)。
下面是 c++ 代码实现：
#include#includeusing namespace std;
int main() {// 读入字符串 s
string s;
cin >>s;
int n = s.size();
// 计算前缀和数组
int prefix[n + 1];
prefix[0] = 0;
for (int i = 1; i<= n; i++) {prefix[i] = prefix[i - 1] + (s[i - 1] == '1');
}
// 计算最少的步数
int steps = 0;
for (int i = 0; i< n; i++) {// 如果当前字符是 1，则将步数加 1
if (s[i] == '1') { steps++;
}
// 否则，枚举以当前字符为起点的子串
else { for (int j = i + 1; j<= n; j++) {// 计算子串中 1 的数量
int ones = prefix[j] - prefix[i];
// 更新答案
steps = min(steps, ones);
}
}
}
// 输出结果
cout<< steps<< endl;
return 0;
}
上面的代码实现了状态转移方程的过程。
注意：
矩阵的行和列都是从 1 开始编号的，所以要注意初始化和转移的时候数组下标的边界。
在转移的时候，需要考虑使用道具的情况。
海神波塞冬拥有着神奇的能力，他能够将一个人的智慧转化成数字，并将这个数字存储在一个无序数组中。但是，有一天，海神波塞冬收到了一个神秘的任务，要求他从这个无序数组中找出最小的 k 个数，并将它们存储在另一个数组中。
题目描述给定一个无序数组 a 和整数 k，你需要在 a 中找出最小的 k 个数，并将它们存储在另一个数组 b 中。
例如，对于数组 [3, 4, 1, 2, 5] 和 k = 3，你可以进行如下操作：
第一步：找出数组中最小的数字 1，将其存储在另一个数组 b 中。
第二步：找出数组中第二小的数字 2，将其存储在另一个数组 b 中。
第三步：找出数组中第三小的数字 3，将其存储在另一个数组 b 中。
因此，最后得到的另一个数组 b 为 [1, 2, 3]。
请在下面编写你的 C++ 代码来解决这道题目：
#include#include
using namespace std;
int main() {// 读入数组 a 和 k
int a[10], k;
for (int i = 0; i< 10; i++) {cin >>a[i];
}
cin >>k;
// 计算最小的 k 个数并存储在另一个数组 b 中
int b[k];
// 在此处编写你的代码
// 输出结果
for (int i = 0; i< k; i++) {cout<< b[i]<< " ";
}
cout<< endl;
return 0;
}
请注意，你的算法的时间复杂度应该尽可能低。
输入格式第一行包含整数 n，表示数组 a 的长度。
第二行包含 n 个整数，依次为数组 a 的元素。
第三行包含整数 k。
输出格式输出一行，包含 k 个整数，依次为数组 b 中的元素。
输入样例5
3 4 1 2 5
31 2 3这道题的题意是，给定一个无序数组 a 和整数 k，你需要在 a 中找出最小的 k 个数，并将它们存储在另一个数组 b 中。
解题思路：
一种方法是使用排序算法将数组 a 排序，然后直接取前 k 个数即可。时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。
另一种方法是使用堆来解决这道题。我们可以将数组 a 中的数字插入到一个大根堆中，然后每次取出堆顶元素，将其存储在数组 b 中。这样，当我们取出了 k 个数字之后，堆中剩余的数字就是最小的 k 个数字。因此，我们可以在每次插入元素之前检查堆的大小，如果堆的大小超过 k，就将堆顶元素弹出。
这种方法的时间复杂度为 O ( n l o g k ) O(nlogk) O(nlogk)，要比前一种方法更优。
下面是使用堆来解决这道题的 C++ 代码：
#include#include
#includeusing namespace std;
int main() {// 读入数组 a 和 k
int n, k;
cin >>n;
int a[n];
for (int i = 0; i< n; i++) {cin >>a[i];
}
cin >>k;
// 计算最小的 k 个数并存储在另一个数组 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;
}
这就是使用堆来解决本题的解法。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧