题意:给定一个数组,数组中的每个数可以加1也可以减1,每次加1或减1记为一次,问要使它们连乘起来乘积为1的最小次数。
思路:很容易想到的是,如果是负数就变为-1,正数变为1,0不变,注意0变为1与变为-1的代价都是1。统计小于0的个数为cnt1,等于0的个数为cnt0。
如果cnt1是奇数,而且0的个数等于0,我们需要把一个-1变为1,这时候代价为各个负数变为-1的代价与各个正数变为1的代价加上0的个数最后加上2即可。
其他情况则的代价是各个负数变为-1的代价与各个正数变为1的代价加上0的个数即可。
AC代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int a[maxn];
int main(void){
int n;
cin>>n;
long long sum = 0;
int cnt1 = 0;
int cnt0 = 0;
for(int i = 1; i <= n; i++){
cin>>a[i];
if(a[i]<0){
sum += -1-a[i];
cnt1++;
}
else if(a[i]==0){
cnt0++;
}
else{
sum += a[i]-1;
}
}
if(cnt1%2&&cnt0==0){
sum += 2;
}
cout<<(sum+cnt0)<<endl;
return 0;
}

京公网安备 11010502036488号