题意:给定一个数组,数组中的每个数可以加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; }