题解 CF1206B 【Make Product Equal One】

· · 题解

题目描述：

给你一个有 n 个数字的数列，你有两种操作：将某个数 +1 或 -1 。求用最小的操作次数让这个数列的每一项乘起来等于 1

n \leq 10^5

解题思路：

用C换来的

分析一下，每个数字只有两种情况：变成 1 或者变成 -1

所以每个数字的代价就是min(abs(1 - a[i]),abs(-1 - a[i]))

值得一提的几个大坑点是，最后可能会变成 -1 ，所以顺便记一下，如果最后变成 -1 了记得加上 2 。而且 0 也要记，最后要加上 0 的个数。

时间复杂度O(n)

代码：

#include <cstdio>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
#define int long long
inline int read() {
    char v = getchar();int x = 0,f = 1;
    while (!isdigit(v)) {if(v == '-')f = -1;v = getchar();}
    while (isdigit(v)) {x = x * 10 + v - 48;v = getchar();}
    return x * f;
}

const int N = 100010;

int pre[N],n,p1,p2,ans,z,res = 1;

signed main() {
    n = read();
    for (int i = 1;i <= n;++i) {
        pre[i] = read();
        if (pre[i] == 0) {
            z++;
        }
    }
    sort(pre+1,pre+1+n);
    for (int i = 1;i <= n;++i) {
        if (pre[i] <= -1) {
            ans += (-1 - pre[i]);
            res *= -1;
        }
        else if (pre[i] >= 1) {
            ans += (pre[i] - 1);
            res *= 1;
        }
    }
    if (res == -1) {
        if (z) {
            ans += z;
        }
        else {
            ans += 2;
        }
    }
    else {
        ans += z;
    }
    cout << ans;

    return 0;
}