数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序查找使所有书籍连续排列的最小移动次数
假设我们有一个包含n个元素的数组A。考虑一个书架，它可以容纳n本书。书架的第i个位置是A[i]，如果该位置有书则为1，否则为0。书架上至少有一本书。在一次移动中，我们可以取某个连续的片段[l到r] -
将它们向右移动1个位置。只有当r右侧有空位时才能执行此操作。
将它们向左移动1个位置：只有当l左侧有空位时才能执行此操作。
我们必须找到将书架上所有书籍收集到一个连续片段所需的最小移动次数。
问题类别
上述问题可以通过应用贪心问题解决技术来解决。贪心算法技术是一种算法类型，其中选择当前最佳解决方案而不是遍历所有可能的解决方案。贪心算法技术也用于解决优化问题，例如它更大的兄弟动态规划。在动态规划中，有必要遍历所有可能的子问题以找出最优解，但它有一个缺点；它需要更多的时间和空间。因此，在各种情况下，使用贪心技术来找出问题的最优解。虽然它并非在所有情况下都能提供最优解，但如果设计得当，它可以比动态规划问题更快地产生解决方案。贪心技术为优化问题提供局部最优解。此技术的示例包括克鲁斯卡尔和普里姆的最小生成树 (MST) 算法、霍夫曼树编码、迪杰斯特拉的单源最短路径问题等。
https://tutorialspoint.com/data_structures_algorithms/greedy_algorithms.htm
https://tutorialspoint.com/data_structures_algorithms/dynamic_programming.htm
因此，如果我们问题的输入类似于 A = [0, 0, 1, 0, 1, 0, 1]，则输出将为 2，因为我们可以将片段 [3 到 3] 向右移动，并将片段 [4 到 5] 向右移动。现在在所有移动之后，书籍形成了连续片段 [5 到 7]。所以答案是 2。
步骤
为了解决这个问题，我们将遵循以下步骤 -
n := size of A ans := 0 Define an empty array v for initialize i := 0, when i < n, update (increase i by 1), do: a := A[i] if a is same as 1, then: insert i at the end of v for initialize i := 1, when i < size of v, update (increase i by 1), do: ans := ans + (v[i] - v[i - 1] - 1) return ans
示例
让我们看看以下实现以更好地理解 -
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
int n = A.size();
int ans = 0;
int a;
vector<int> v;
for (int i = 0; i < n; i++){
a = A[i];
if (a == 1)
v.push_back(i);
}
for (int i = 1; i < v.size(); i++)
ans += (v[i] - v[i - 1] - 1);
return ans;
}
int main(){
vector<int> A = { 0, 0, 1, 0, 1, 0, 1 };
cout << solve(A) << endl;
}输入
{ 0, 0, 1, 0, 1, 0, 1 }输出
2
215 次查看
