寒光博客

[Codeforces]#580 (Div. 2) B. Make Product Equal One
B. Make Product Equal One https://codeforces.com/contest/...
扫描右侧二维码阅读全文
18
2019/08

[Codeforces]#580 (Div. 2) B. Make Product Equal One

B. Make Product Equal One
https://codeforces.com/contest/1206/problem/B

题目

time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given n numbers a1,a2,…,an. With a cost of one coin you can perform the following operation:

Choose one of these numbers and add or subtract 1 from it.

In particular, we can apply this operation to the same number several times.

We want to make the product of all these numbers equal to 1, in other words, we want a1⋅a2 … ⋅an=1.

For example, for n=3 and numbers [1,−3,0] we can make product equal to 1 in 3 coins: add 1 to second element, add 1 to second element again, subtract 1 from third element, so that array becomes [1,−1,−1]. And 1⋅(−1)⋅(−1)=1.

What is the minimum cost we will have to pay to do that?

Input

The first line contains a single integer n (1≤n≤105) — the number of numbers.

The second line contains n integers a1,a2,…,an (−109≤ai≤109) — the numbers.

Output

Output a single number — the minimal number of coins you need to pay to make the product equal to 1.

分析

其中最重要的就是0的转化 0的变化量为1 但是他可以向+or-转化,其中-就是关键点了
如自测点

5
-1 -1 -2 0 1

如果0的个数大于0并且负数为奇数 那么需要一个0向-1转化 虽然加的0的个数还是一样 但是其中意义不同,导致 你不需要把最小的负数化为1 只要化为-1即可
但是如果没有0 那么你这个-1只能乖乖话为1了
上述也就是我wa了两次的原因,感谢 十元 dalao的指点

如果0的个数为0
就需要把一个-1变成1
这样子代价才是最小

AC代码

package cf._580D2;

import java.util.Scanner;
//1274968094
import static java.lang.Math.abs;
import static java.util.Arrays.sort;

public class B {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int[] fu = new int[n];
        int f = 0;
        long ans = 0, fans = 0;
        int zeroCount = 0;
        for (int i = 0; i < n; i++) {
            int x = cin.nextInt();
            if (x < 0) {
                fu[f++] = x;
                fans += abs(x) - 1;
            } else {
                if (x == 0) {
                    zeroCount++;
                }
                if (x > 1) {
                    ans += x - 1;
                }
            }
        }
        if (f % 2 == 0) {
            System.out.println(ans + fans + zeroCount);
        } else {
            int[] rec = new int[f];
            for (int i = 0; i < f; i++) {
                rec[i] = fu[i];
            }
            sort(rec);//- 16 -15
            for (int i = 0; i < f - 1; i++) {
                ans += abs(rec[i]) - 1;
            }
            if (zeroCount != 0) {//有0
                ans += abs(rec[f - 1]) - 1;
                System.out.println(ans + zeroCount );//其中一个0是 转-1,
            } else {//没0 最小-x 变1
                ans += abs(rec[f - 1]) + 1;
                System.out.println(ans);
            }
        }

    }
}

cf十元

十元dalao的代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
int c[N];
int vis[3];
int main()
{
    int n;
    scanf("%d", &n);
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &c[i]);
        if (c[i] < 0)
        {
            ans += (-1 - c[i]);
            c[i] = -1;
            vis[2]++;
        }
        else if (c[i] > 0)
        {
            ans += (c[i] - 1);
            c[i] = 1;
            vis[1]++;
        }
        else
            vis[0]++;
    }
    if (vis[2] % 2 == 0)
        ans += vis[0];
    else if (vis[2] % 2 != 0)
    {
        if (vis[0] != 0)
            ans += vis[0];
        else
            ans += 2;
    }
    printf("%lld", ans);
}

感觉

这次 AB题写起来 都有思路 很快反映过来 但是最后wa了 就很懵
再请教大佬细节 ,,问题就变得很简单,,这种思维的~~ 嗯 只能多练了。
A题就不记录了 求出最大值即可

本文作者:Author:     文章标题:[Codeforces]#580 (Div. 2) B. Make Product Equal One
本文地址:https://dxoca.cn/Algorithm/254.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:August 19th, 2019 at 12:04 am
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment