給定一個整數序列，計算使所有數字都為 0 所需的最少操作次數。一個操作如下：將索引 i 到索引 j 的所有數字增加或減少 1。
示例 1)
{1, 1, -1}
你可以做：
減少索引 0 到 1
將索引 2 增加到 2
所以答案是2個操作。
例 2)
{3, -1, -1, 3}
減少索引 0 到 3
減少索引 0 到 3
減少索引 0 到 3
增加索引 1 到 2
增加索引 1 到 2
增加索引 1 到 2
增加索引 1 到 2
所以答案是7。
什么是有效的演算法來做到這一點？
uj5u.com熱心網友回復：
一個問題是有很多方法可以使最終結果為 0，即使在所有情況下都使用最少的操作次數。
例如，對于{1, 0, 1}我們的應用-1上[0, 2]，并 1上[1, 1]
或者我們可以應用-1上[0, 0]，再-1上[2, 2]。
在這兩種情況下，都需要進行兩次操作。
由于只需要最少數量的操作，我們可以決定在不同的時間間隔內拆分操作，只要它看起來不是次優的。
然后，通過比較相鄰索引之間的值，應用迭代程序。
例如，如果符號不同，或者如果新值是0，我們可以決定拆磁區間。
#include <iostream>
#include <vector>
int count_operations (const std::vector<int> &A) {
int n = A.size();
if (n == 0) return 0;
int count = std::abs (A[0]);
for (int i = 1; i < n; i) {
if (A[i]*A[i-1] > 0) {
if(std::abs(A[i]) > std::abs(A[i-1])) {
count = std::abs(A[i]) - std::abs(A[i-1]);
}
} else {
count = std::abs(A[i]);
}
}
return count;
}
int main() {
std::vector<int> A = {1 , 1, -1};
auto ans = count_operations (A);
std::cout << ans << "\n";
A = {3, -1, -1, 3};
ans = count_operations (A);
std::cout << ans << "\n";
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/387591.html
上一篇：在嵌套函式中傳遞資料
下一篇：分明滅燈