数据结构
网络
关系数据库管理系统
操作系统
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 次查看
广告