Решение задачи "Сделайте произведение единицей" с Codeforces

Без пояснения   Просмотров: 10


Даны n целых чисел a1,a2,…,an. За одну монету можно сделать следующую операцию:

Выбрать одно из этих чисел, и уменьшить или увеличить его на 1.

В частности, мы можем применять эту операцию к одному и тому же числу несколько раз.

Мы хотим добиться того, чтобы произведение всех чисел стало равно 1, другими словами, чтобы a1⋅a2 … ⋅an=1.

К примеру, для n=3 и чисел [1,−3,0] мы можем сделать произведение равным 1 за 3 монеты: добавить 1 к второму элементу, добавить 1 к второму элементу еще раз, отнять 1 от третьего элемента, в результате чего массив станет равным [1,−1,−1]. А 1⋅(−1)⋅(−1)=1.

Какое минимальное количество монет нужно для этого заплатить?

Код

#include <bits/stdc++.h>

using namespace std;

int main()
{
    long long n, temp, p, o , z, minp, minpi, mino = -1,minoi = -1;
    p = o = z = 0;
    minp = mino = 9000000000000;
    cin >> n;
    vector<long long > a;
    for(long long i = 0; i < n; ++i){
        cin >> temp;
        if(temp > 0){
            if(minp > temp){
                minp = temp;
                minpi = i;
            }
            ++p;
        }
        else if(temp < 0){
            if(mino > temp){
                mino = temp;
                minoi = i;
            }
            ++o;
        }
        else
            ++z;
        a.push_back(temp);
    }
    if(n == 1 && o == 1){
        if(a[0] < 1){
            cout << abs(a[0]) + 1;
            return 0;
        }
    }
//    cout << p << " " << o << " " << z << endl;
    long long res = 0;

    if(!z){
        if(o % 2){
            if(p){
                if(minp < abs(mino)){
                    a[minpi] = minp + 1;
                    res+=abs(minp) + 1;
                    a.erase(a.begin() + minpi);
                }
                else{

                    a[minoi] = mino + 1;
                    res+=abs(mino) + 1;
                    a.erase(a.begin() + minoi);
                }
            }
            else{
                a[minoi] = mino + 1;
                res+=abs(mino) + 1;
                a.erase(a.begin() + minoi);
            }
        }
        else{

        }
    }
    else{
        if(o % 2 == 0){
            res+=z;
            z = 0;
        }
        else{
            res+=z;
        }
    }
    for(long long i = 0; i < a.size(); ++i){
        if(a[i] > 1){
           res+= a[i] - 1;
        }
        if(a[i] < -1){
            res+=abs(a[i]) - 1;
        }
    }
//    cout << p << " " << o << " " << z << endl;
    cout << res;
    return 0;
}
/* comments
    1
    -1000000000

    4
    -1  1 -1 1                  =>  0


    3
    -3 1 1                      =>  4

    4
    -10 5 0 1                   =>  10

*/
/*
    2 2 0    if(!z) if(o % 2 == 0){ nothing; }
    0 2 1    if(z)  if(o % 2 == 0){ res+=z; z = 0;}
    2 3 0    if(!z){
                if(o % 2){
                    if(p){
                        if(minp < abs(mino)){
                            a[minpi] = minp + 1;
                            res+=minp + 1;
                        }
                        else{
                            a[minoi] = mino + 1;
                            res+=mino + 1
                        }
                    }
                    else{
                            a[minoi] = mino + 1;
                            res+=mino + 1;
                        }
                }

            }
            else{
                if(z)
                    if(o % 2 == 0){
                        res+=z;
                        z = 0;
                    }
            }
*/

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться