資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚學
法律學C++程式計算滿足給定條件所需的最少操作次數
假設我們有一個包含N個元素的陣列A。在每次操作中，我們選擇一個元素並將其增加或減少1。我們需要找到滿足以下條件所需的最少操作次數：
對於1到n範圍內的每個i，從第1項到第i項的總和不為0。
對於1到n-1範圍內的每個i，從第1項到第i項的總和的符號與從第1項到第(i+1)項的總和的符號不同。
因此，如果輸入類似於A = [1, -3, 1, 0]，則輸出將為4，因為我們可以透過四次操作將序列轉換為1, -2, 2, -2。前一、二、三和四項的總和分別為1, -1, 1和-1。
步驟
為了解決這個問題，我們將遵循以下步驟：
n := size of A ret := 0 sum := 0 for each ai in A, do nsum := sum + ai if s > 0, then: if nsum <= 0, then: ret := ret + |nsum| ai := ai + |nsum| Otherwise if nsum >= 0, then: ret := ret + nsum + 1 ai := ai - (nsum + 1) sum := sum + ai s := s * -1 return ret
示例
讓我們看看以下實現以獲得更好的理解：
#include <bits/stdc++.h>
using namespace std;
int util(vector<int> A, int s){
int n = A.size();
int ret = 0;
int sum = 0;
for (int ai : A){
int nsum = sum + ai;
if (s > 0){
if (nsum <= 0){
ret += abs(nsum) + 1;
ai = ai + abs(nsum) + 1;
}
} else{
if (nsum >= 0){
ret += nsum + 1;
ai = ai - (nsum + 1);
}
}
sum += ai;
s *= -1;
}
return ret;
}
int solve(vector<int> A){
int res = min(util(A, 1), util(A, -1));
return res;
}
int main(){
vector<int> A = { 1, -3, 1, 0 };
cout << solve(A) << endl;
}輸入
{ 1, -3, 1, 0 }輸出
4
更新於: 2022年3月3日
154 次檢視
廣告