資料結構
網路
關係資料庫管理系統
作業系統
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.tw/data_structures_algorithms/greedy_algorithms.htm
https://tutorialspoint.tw/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 次檢視
