[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.

分析

5
-1 -1 -2 0 1

如果0的个数为0

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十元

#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);
}

感觉

A题就不记录了 求出最大值即可

百度已收录

Last modification：August 19th, 2019 at 12:04 am